[Algorithm] Baekjoon 2493번 : 탑

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

2493번: 탑

 

int answer[500001] = { 0 };
 
struct Node
{
    int num;
    int index;
};
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n; 
 
    stack<Node> s1;
    stack<Node> s2;
    int input;
 
    cin >> n;
 
    if (n == 1)
    {
        cout << 0;
        return 0;
    }
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> input;
        s1.push({ input,i });
    }
 
    while (s1.size() != 1)
    {
        s2.push(s1.top());
        s1.pop();
 
        while (!s2.empty() && s1.top().num > s2.top().num)
        {
            answer[s2.top().index] = s1.top().index;
            s2.pop();
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        printf("%d ", answer[i]);
    }
}

골드5 스택문젠데.. 공책에 대충 끄적이니 금방 해결하긴 했다. 풀고나니 그냥 스택 한개로 더 간단하게 짤 수 있을 것 같긴하다.

 

쨌든 위의 풀이는 스택 두개 이용해서 한 풀이인데, 입력값들을 전부 인덱스랑 같이 구조화해서 (pair를 쓰든 구조체로 만들든.. 난 무조건 구조체로 만드는걸 선호한다) 스택(s1)에 넣어준다.

이후 반복문을 수행할 건데, 일단 두번째 스택(이하 s2)에다 s1의 top을 꺼내서 넣고, s2의 top과 s1의 top을 비교해준다.

s2의 top이 더 작다면, 즉 s1이 보낸 신호를 s2가 받을 수 있다면 정답에 기록을 해주고 s2를 pop한다(수신됐으니까).

그리고 한번만 하는게 아니라, s2에는 아직 신호를 송신하지못한것들이 남아있기 때문에 수신할 수 있는 안테나들은 계속 수신해준다.

 

해당 로직은 수행하기 전에 s1의 크기가 반드시 2이상이여야 하니 1이 되면 바로 로직을 끝내준다.

s1에 하나밖에 안들어있다면, 비교군이 더이상 없다는 것이기 때문에..  s2와의 비교는 이전 반복문때 끝냈으니 신경 쓸 필요없다.