[백준 BOJ] 17298 오큰수 C++

문제

---

https://www.acmicpc.net/problem/17298

 

입력

• 수열 A의 크기
• 수열 A의 원소들

출력

• Ai의 오큰수
  • 오큰수: Ai의 오른쪽에 있고, Ai보다 큰 수이며, 큰 수들 중 가장 왼쪽에 있는 수
• 오큰수가 없는 경우 -1 출력

 

---

 

풀이

---

• 수열의 원소는 배열에 저장, 인덱스는 스택에 저장해 문제를 해결한다.
• 스택에 저장되어 있는 수는 오큰수를 찾지 못한 원소이다.

 

세부 풀이

• 배열에 수열의 원소 저장한다.
  • 이때 문제에 제시된 수열의 크기를 배열의 크기로 지정한다. (1 ≤ N ≤ 1,000,000)
  • 인덱스를 이용해 원소의 크기를 비교할 예정이기 때문에 인덱스 사용이 용이하도록 자료구조는 배열로 선택했다.
• 원소의 인덱스를 스택에 저장한다.
  • 앞 원소(Ai-1)와 현재 원소(Ai)를 비교하기 위해 스택을 사용했는데, 스택은 LIFO(Last In First Out)으로 이미 스택에 저장된 값을 비교할 수 있다.
• 0번 인덱스를 가장 먼저 스택에 저장했다.
• 스택이 비어있지 않고, 이미 스택에 저장된 원소(Ai-1)와 현재 원소(Ai)의 값을 비교한다.
• Ai-1가 Ai보다 작다면 결과 배열에 Ai를 저장한 후 스택에서 i-1을 제거해준다.
• N번 동안 비교를 한 후 스택에 남아있는 원소가 있다면 이 원소는 오큰수가 없는 원소이므로 결과 배열에 -1을 저장해준다.

 

코드

---

#include <iostream>
#include <stack>
#define MAX 1000001
using namespace std;

int N;
int arr[MAX]={0,};
int nge[MAX]={0,};
stack <int> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;

    for (int i=0;i<N;i++) {
        cin >> arr[i];
    }

    for (int i=0;i<N;i++) {
        while (!s.empty() && arr[s.top()]<arr[i]) {
            nge[s.top()] = arr[i];
            s.pop();
        }
        s.push(i);
    }

    while (!s.empty()) {
        nge[s.top()] = -1;
        s.pop();
    }

    for (int i=0;i<N;i++){
        cout << nge[i] << " ";
    }

    return 0;
}

 

---

 

사실 처음에는 시간초과가 나왔었다.

냅다 이중 for문을 쓰는 바람에 시간 복잡도가 O(N^2)이 되어 30%쯤에서 시간초과가 나왔던 것 같다.

그리고 내가 봐도 내 코드가 별로였다.
자료구조로 벡터를 사용했는데 벡터의 장점을 활용하지 못하고 배열처럼 사용했다. 

flag 변수 사용하는거 안 좋아하는데 일단 코드를 돌리려고 flag 변수도 사용해버렸다. 

앞으로는 자료구조를 백번 활용할 수 있도록 왜 이 자료구조를 사용하는지 고민하는 연습을 해야겠다!!

내가 봐도 별로였던 코드.. 부끄럽지만 첨부합니다🤧

#include <iostream>
#include <vector>
using namespace std;

int N;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    vector <int> v(N);

    for (int i=0;i<N;i++){
        cin >> v[i];
    }

    int size = v.size()-1;
    for (int i=0;i<N;i++){
        int flag = false;
        int cur = v[i];

        for (int j=i;j<N;j++){
            if (cur < v[j+1]){
                cout << v[j+1] << " ";
                flag = true;
                break;
            }
        }

        if (i == size || !flag){
            cout << "-1 ";
        }
    }
    cout << '\n';

    return 0;
}