백준 17298번 오큰수 (C++)

문제 링크 : https://www.acmicpc.net/problem/17298

17298번: 오큰수

문제 요약

 

1. 어느 한 숫자의 오른쪽에 위치한 숫자 중, 가장 왼쪽에 위치한 큰 숫자가 해당 숫자의 오큰수가 됩니다.

2. 만약 오큰수가 존재하지 않을 경우, 해당 숫자의 오큰수는 -1이 됩니다. 

3. 예시는 다음과 같습니다.

ex) 3 5 8 -> (각 숫자의 오큰수의 값) : 5 8 -1

 

핵심 포인트

 

다음 문장을 순차적으로 이해하여 하나씩 구현하면 됩니다. 스택을 사용하면 쉽게 풀 수 있습니다.

어느 한 숫자의 (1) 오른쪽에 위치한 숫자 중, (2) 가장 왼쪽에 위치한 (3) 큰 숫자가 해당 숫자의 오큰수

 

문제 풀이

 

1. 필요한 변수들을 선언하고 값을 입력 받습니다.

변수들의 핵심 설명은 다음과 같습니다.

int n=0,temp=0,now=0;
    stack<int> st;
    cin >> n;
    vector<int> v(n); // 1
    vector<int> ans(n); // 2
    int pos = n-2; // 3
    for (int i = 0; i < n; i++) cin >> v[i];
    st.push(v[v.size() - 1]); // 4
    ans[n-1] = -1; // 5

(1) 값을 입력받을 벡터입니다.

(2) 정답(각 숫자의 오큰수)을 저장할 벡터입니다.

(3) 해당 pos부터 0까지, 즉, 맨 오른쪽 숫자부터 왼쪽 숫자까지 순차적으로 오큰수를 구해나갑니다. n-2부터 오큰수를 판단하는 이유는, v[n-1]은 오른쪽에 더 이상 숫자가 없으므로, 이미 -1로 정답이 정해져있기 때문입니다.

(4) 스택에 v벡터의 가장 오른쪽 값을 저장합니다.

(5) 벡터의 가장 오른쪽 값의 오큰수는 -1입니다.

 

2. 다음은 각 숫자별로 오큰수를 구하는 로직입니다.

while (pos>=0) { // 1
        temp = st.top(); // 2
        now = v[pos];
        if (temp > now) {
            ans[pos] = temp; // 3
            st.push(now);
        }
        else {
            while (!st.empty()) { // 4
                temp = st.top(); // 5
                if (temp <= now) st.pop(); // 6
                else {
                    ans[pos] = st.top(); // 7
                    break;
                }
            }
            if (st.empty()) ans[pos] = -1; // 8
            st.push(now); // 9
        }
        pos--; // 10
    }

(1) while문은 0번째 숫자가 오큰수를 구할때까지 진행됩니다.

(2) 현재 스택의 최상단의 값을 temp에 저장합니다.

(3) 벡터의 현재 위치(pos)에 위치한 값을 now에 저장합니다.

(3) 만약 temp가 현재 값보다 클 경우, temp는 now의 오큰수가 됩니다. 오큰수를 저장하고 now를 스택에 저장합니다.

(4) 만약 temp가 현재 값보다 작을 경우, while문을 한번 더 진행합니다. 조건은 스택이 빌때까지 입니다.

-> (5) 스택의 최상단의 값은 temp에 저장합니다.

-> (6) 만약 temp가 현재값의 이하일 경우, 스택을 pop합니다.

참고로 <=이 아닌 <로 표기할 경우 틀립니다. 오큰수는 무조건 큰 숫자만 가능하기 때문입니다.

-> (7) 만약 temp가 현재값보다 클 경우, temp는 now의 오큰수가 됩니다. 오큰수를 저장하고 while문을 종료합니다.

-> (8) 만약 스택이 비었을 경우, 오큰수를 찾지 못했다는 뜻이므로 -1을 저장합니다.

-> (9) 현재 값을 스택에 저장합니다.

(10) pos의 값을 -1합니다.

 

+ 참고로 7~9의 과정을 그림으로 요약하자면 다음과 같습니다.

(11) 0부터 n-1까지 정답을 출력합니다.

for (int i = 0; i < n; i++) cout << ans[i] << " ";

 

 

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n=0,temp=0,now=0;
    stack<int> st;
    cin >> n;
    vector<int> v(n);
    vector<int> ans(n);
    int pos = n-2;
    for (int i = 0; i < n; i++) cin >> v[i];
    st.push(v[v.size() - 1]);
    ans[n-1] = -1;
    while (pos>=0) {
        temp = st.top();
        now = v[pos];
        if (temp > now) {
            ans[pos] = temp;
            st.push(now);
        }
        else {
            while (!st.empty()) {
                temp = st.top();
                if (temp <= now) st.pop();
                else {
                    ans[pos] = st.top();
                    break;
                }
            }
            if (st.empty()) ans[pos] = -1;
            st.push(now);
        }
        pos--;
    }
    for (int i = 0; i < n; i++) cout << ans[i] << " ";
    return 0;
}

이 코드는 208ms가 소비되었습니다.