[백준 17298번] 오큰수

---

문제 화면

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

문제 풀이

이 문제는 stack의 자료구조를 응용하는 문제이다. 문제의 핵심은 현재 숫자 기준으로 오큰수를 찾는 것이 아닌 오큰수가 되는 숫자 관점에서 생각해야 되는 부분이다. 스택 특성상 왼쪽에서 오른쪽을 생각했을 때 풀이가 떠오르지 않으면 오른쪽에서 왼쪽으로 생각하면 풀리는 경우가 많은 것 같다.

기존의 스택 문제들과 큰 차이가 없어서 문제를 푸는 데에 큰 어려움은 없었지만 문제를 풀고 나서 다른 사람들의 코드와 비교하면서 내 코드가 여러 부분에서 비효율적이라는 생각이 들어서 최적화를 해보았다. 문제를 맞추는 것에 만족하는 것이 아닌 맞추고 나서 어떻게 하면 더 좋은 코드가 될 수 있었을까 복기하는 습관도 중요한 것 같다.

제출 코드

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

vector<int> v;
stack<int> p;
stack<int> s;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int a, temp;
    cin >> a;
    for(int i = 0 ; i < a ; i++) {
        cin >> temp;
        v.push_back(temp);
    }

    for(int i = v.size()-1 ; i >=0 ; i--) {
        if(s.empty()) p.push(-1); // 마지막 번호는 무조건 -1이기 때문에 넣어준다. 

        while(!s.empty()) {
            if(s.top() > v[i]) {
                p.push(s.top()); 
                break;
            } // 찾으면 while문 나가라
            else {
                s.pop();
                if(s.empty()) {
                    p.push(-1);
                }
            }
        } // 오큰수 찾을때까지 pop

        s.push(v[i]);
    }

    while(!p.empty()) {
        cout << p.top() << " ";
        p.pop();
    }
        
    return 0;
}

제출 코드(최적화)

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

// vector<int> v;
// stack<int> p;

int A[1000001];
int P[1000001];
// 배열이 더 빠르다. 굳이 벡터나 스택 쓰지 말자. 

stack<int> s;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int a;
    cin >> a;
    for(int i = 0 ; i < a ; i++) cin >> A[i];
       

    for(int i = a-1 ; i >=0 ; i--) {
        
        while(!s.empty() && s.top() <= A[i]) s.pop(); 
        // empty()와 크기를 동시에 비교
        // 코드가 더 짧아지고 기존 코드와 같이 pop() 조건을 두번씩 확인할 필요가 없음
        // 이 while문을 빠져나가면 1. 스택이 비어있거나 2. 더 큰 오큰수만 남게 된다. 
        
        if(s.empty()) P[i] = -1;
        // 1. 스택이 비어있는 경우 오큰수가 없다는 뜻이기 때문에 -1을 정답 배열에 저장
        // 주의할 점은 s.top()을 확인하기 전에 empty()를 먼저 확인해주어야 한다!(처음에 s.top()을 먼저 넣어주어서 오답이 떴다)

        else P[i] = s.top(); 
        // 2. 더 큰 오큰수만 남아있는 경우이기 때문에 바로 정답 배열에 넣어주면 된다. 

        s.push(A[i]);
        // 현재 숫자를 스택에 넣어준다. 
    }

    for(int i = 0 ; i < a ; i++) {
        cout << P[i] << " ";
    }
        
    return 0;
}

결론

다른 스택 문제들과 크게 다르지 않았지만 코드를 최적화 할 수 있는 부분들을 찾아서 앞으로 문제를 풀 때 많은 도움이 될 것 같다.

출처

• https://cocoon1787.tistory.com/347