백준 17298번: 오큰수

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

참조한 블로그 : https://st-lab.tistory.com/196

스택 문제로 분류돼서 풀어보는데 어디에 스택을 사용해야하는지 감이 잡히지 않는 문제였다. 생각나는대로 풀어보았으나 역시나 시간초과가 떴고, 검색을 해서 답을 보고 이해한 후 코드를 작성했다.

이해한 대로 간단하게 설명하면, index 0번부터 n-1번까지 전체 수열을 탐색하면서 현재 원소가 이전 원소보다 작으면 스택에 현재 원소의 index를 push한다. 현재 원소가 이전 원소보다 크면 스택에 들어있는 값을 pop하면서 현재 원소와 비교한 후 현재 원소가 더 크다면 스택에서 pop한 값을 현재 원소의 값으로 바꾸어준다.

if(현재 원소 < 이전 원소)
   stack.push(현재 원소의 index)
   
else
   if(stack.top() < 현재 원소)
      stack.top()번째 값 = 현재 원소

이것을 반복하면서 수열 전체를 탐색하고, 탐색이 끝났을 때 스택에 남아있는 index들은 해당 index의 값보다 큰 숫자가 없다는 뜻이므로 -1로 바꾸어주면 원하는 답을 구할 수 있다.

<작성한 코드>

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

int main()
{
    int n;
    vector<int> v;
    stack<int> s;
    cin >> n;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        v.push_back(temp);
    } // 수열 입력
    
    for(int i = 0; i < n; i++){
    	// if(stack.top() < 현재 원소) 부분
        while(!s.empty() && v[s.top()] < v[i]){
            v[s.top()] = v[i];
            s.pop();
        }
        s.push(i); // if(현재 원소 < 이전 원소) 부분
    }
    
    // 더 큰 숫자가 없는 index들 -> -1로 값 변경
    while(!s.empty()){
        v[s.top()] = -1;
        s.pop();
    }
    
    for(int i = 0; i < n; i++)
        cout << v[i] << " ";
}

설명을 잘 못 써서 이해하기 어려운데, 참고한 블로그에 정리가 잘 되어있으므로 가서 읽어보면 금방 풀 수 있을 것이다.

아직은 이 정도 문제도 스스로 풀지 못하는구나 느끼게 된 문제였다.. 많이 풀다보면 어떻게는 되겠지 뭐. velog 처음 써보는데 html 처럼 작성할 수 있는게 상당히 신기하다. span 이런것도 되고 위에 링크 다는 것도 되고 암튼 신기하다.

앞으로도 스스로 풀지 못하고 검색해서 푼 문제들은 정리를 따로 해둬야겠다.