[BOJ 17298] 오큰수

17298번: 오큰수

문제 분석

• 시간제한 1초 : Big-O 기준 연산 약 1억번
• 다뤄야 할 수들 : 1,000,000 -> 단순 이중 반복문 불가
• 각 수마다 할당되는 오큰수
• 어떤 수 A의 오큰수를 찾을 때 오른쪽에 있는 수 중 A보다 작은 수는 A의 왼쪽에 있는 오큰수가 될 수 없다.

풀이 방식

• <stack> 사용
• 배열의 오른쪽부터(마지막 인덱스부터) 오큰수를 찾을때까지 반복
  • stack.top이 원소의 값보다 크면 이 원소의 오큰수는 stack.top
  • 작거나 같으면 pop

주의 사항

• 오큰수를 찾지 못하면 그 수의 오큰수는 -1 : 오큰수를 찾는 과정에서 스택이 비어버리면 오큰수는 -1

stack<int> nge;//오큰수 후보가될 스택
vector<pair<int, int>> arr;//(값,오큰수)
int n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.emplace_back(x, -1);//초기값 -1
    }
    for (int i = (int) arr.size() - 1; i >= 0; i--) {
        while (!nge.empty()) {//스택이 빌때까지 오큰수를 찾아보자
            if (nge.top() > arr[i].first) {//스택의 top이 원소의 값보다 크면
                arr[i].second = nge.top();//해당 원소의 오큰수는 스택의 top
                break;//오큰수 찾으면 반복문 stop
            } else {
                nge.pop();
                //i번 원소보다 작은 값은 i번 원소의 왼쪽에 있는 값의 오큰수가 될수 없다.
            }
        }
        nge.push(arr[i].first);//i번 원소 스택에 쌓아주자
    }
    for (int i = 0; i < n; i++) {
        cout << arr[i].second << " ";
    }
    return 0;
}

느낀 점

• 사실 이 문제는 오른쪽 부터 <stack>을 이용해 접근하라는 힌트를 얻어 풀기 시작했다.
• 오큰수 배열과 <stack>의 그림을 그리며 어떻게 풀까 고민을 하다보니 " 어떤 수 A의 오큰수를 찾을 때 오른쪽에 있는 수 중 A보다 작은 수는 A의 왼쪽에 있는 오큰수가 될 수 없다. " 는 점을 꽤 빨리 생각해냈다.
• 처음에 뒤에서 부터 접근하라는 힌트를 얻지 않은 상태에서 풀었으면 시간제한에 맞춰 푸는데 시간이 꽤 걸렸을 거 같다.