오큰수(x)

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

#include<iostream>
#include<vector>
#include<stack>
#include<memory.h>
using namespace std;
int n;
vector<int> v;
int arr[1000001];
stack<int> s;

int main()
{   
    cin>>n;
    v.resize(n,0);
    memset(arr,-1,sizeof(arr));
    for(int i=0;i<n;i++)
    {
        cin>>v[i];

        while(s.empty() == false && v[s.top()] < v[i])
        {
            arr[s.top()] = v[i];
            s.pop();
        }
        s.push(i);
    }

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

• 문제를 쉽게 생각해서 반복문을 여러개 이용해 풀었더니 시간초과가 났다
• 그래서 살짝 힌트를 봤더니 Stack을 이용하는 문제였다
• 값들을 입력 받을 때 마다 Stack이 비어있는지, s의 top을 index로 검색했을 때 값과 현재 들어온 값을 비교해 현재 들어온 값이 크다면 오큰수가 된 것이므로 while 문 안으로 들어간다
• 이 안에서는 arr에 s.top()을 index로 사용해 현재 입력받은 값을 저장한 뒤 s.pop()을 통해 Stack에 있는 값을 빼준다
• 이렇게 하면 오큰수를 만나면 배열에 순서대로 오큰수를 저장할 수 있다
• 반복문이 끝나면 s에 i를 저장해주면 된다

접기/펼치기

이 문제는 짝짓기 문제이다.
 그 이유는 배열을 돌면서 자기 자신보다 크면서 가장 왼쪽에 있는 값을 찾아 배열에 저장하는 문제이기 때문에 짝을 짓는 것이라 볼 수 있다 
 짝짓기 문제의 팁은 왠만하면 Stack으로 풀린다
 하지만 일단 먼저 무식하게 풀어봐야한다. 즉 for문으로 때려박아 만들어 봤더니 시간초과가 떴다
 그래서 Stack으로 풀기위해 문제를 해석해보자. 1. 오큰수가 없다면 일단 Stack에 담아놓는다, 2. 결정이 되면 그땐 오큰수 이므로 배열등에 담아놓는다
 이 조건을 가지고 문제를 풀면 시간초과 없이 잘 풀리는 것을 볼 수 있다