백준 2493 - 탑

🔐 백준 2493 - 탑

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

🔑 첫 풀이

첫 풀이는 정답을 저장할 stack 하나와 탑의 정보를 저장할 vector 하나를 이용하여

문제에 접근하였다. 아래와 같이 각각의 탑에 대해 신호를 수신할 탑을 만날때까지

반복문을 이용하여 접근하도록 하는 이중 반복문 풀이를 사용했다.

N의 범위가 500,000 이하였기 때문에 당연히 시간 제한에 걸리게 되는 것을 알고 있었지만,

다른 풀이가 생각나지 않았다.

stack<int> result;
vector<pair<int, int>> st;

for (int i = 0; i < N; ++i) {
    int target = st[N - 1 - i].first;
    int idx = N - 2 - i;

    if (i == N - 1) {
        result.push(0);
        break;
    }

    while (true) {
        if (target <= st[idx].first) {
            result.push(st[idx].second + 1);
            break;
        }
        if (idx == 0) {
            result.push(0);
            break;
        }
        idx--;
    }
}

🔑 두번째 풀이

무조건 $ O(N^2) $ 의 풀이는 피해야 한다고 생각했고, 모든 값들을 저장하고, 확인해야

할까? 라는 생각을 하게 되었다. 첫 번째 풀이에서는 마지막 입력 값부터 구했지만,

그럴 필요가 없었다. 첫 번째 입력값부터 차례로 받고, 입력 받는 즉시 stack 안의 값과

비교하여 바로바로 출력해 주면 된다. 문제를 푼 알고리즘은 다음과 같다.

1. 값을 입력받음 -> 스택 체크
    if 스택이 비어있음 -> 현재 탑 왼쪽에는 탑이 없다. -> 0 출력

    else 탑이 존재 -> 현재 탑과 스택 top의 높이 비교
        if 현재 값보다 작다면 -> pop -> 다음 값 비교
        else 크다면 -> 출력

2. 현재 탑 push

3. 1 ~ 2 를 N번 반복

코드