백준 #17299 (C++)

1. 문제

2. 풀이 및 소스 코드

- stack을 이용해서 푸는 문제였다. N개만큼 입력을 받아서 stack에 넣어줬다. 다만 빈도를 알아야 하기 때문에 해당 값을 index로 갖는 배열을 +1 해줬다. 이후 stack이 비어있지 않을 동안 while문을 진행했다.

List라는 이름을 갖는 stack도 만들어줘서 기존 S stack에서 빼낸 것 중 유효한 것은 List에 넣어줬다. 만약 List.top()을 index로 갖는 Count배열의 값이 S.top()을 index로 갖는 Count배열의 값 이하라면 유의미한 값이 아니므로 List에서 빼주고 S.top()의 값을 List에 넣어줬다. 그게 아니라면 정답을 저장하는 Sol stack에 List.top()을 넣어주고, List에는 S.top()의 값을 넣어줬다.

#include <iostream>
#include <stack>
#include <vector>

int Count[1000001] = { 0, };
std::stack <int> S;
std::stack <int> List;
std::stack <int> Sol;
int N;

void Input() {
    std::cin >> N;
    for (int i = 0; i < N; i++) {
        int X;
        std::cin >> X;
        S.push(X);
        Count[X]++;
    }
}

void Solve() {
    while (!S.empty()) {
        if (List.empty()) {
            List.push(S.top());
            Sol.push(-1);
        }
        else {
            while (true) {
                if (Count[List.top()] <= Count[S.top()]) {
                    List.pop();
                    if (List.empty()) {
                        Sol.push(-1);
                        List.push(S.top());
                        break;
                    }
                }
                else {
                    Sol.push(List.top());
                    List.push(S.top());
                    break;
                }
            }
        }
        S.pop();
    }
    while (!Sol.empty()) {
        std::cout << Sol.top() << " ";
        Sol.pop();
    }
}

int main() {
    Input();
    Solve();
}

3 느낀 점

- 문제 풀 때보다 글로 설명하는 과정이 더 어려운 문제였다. 이러한 과정이 귀찮긴 하지만 문제에 대한 생각을 정리하는 데에 큰 도움이 되는 것 같다.