2493 탑

2943. 탑 / c++ / Gold5 / 12분 / 20등

문제

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

1. 서로 다른 길이의 탑이 N개 주어진다.
2. 아래의 조건을 정보에 담는다.
   1. 자신보다 왼쪽에 있는 탑 중
   2. 자신보다 크고
   3. 자신과 가장 가까이 있는 탑의 위치
3. 정보 출력

접근 방식

자료구조, 연결 리스트

1. 모든 탑마다 왼쪽으로 자신보다 큰 탑을 탐색해야 하나 생각했다.
2. 생각해보니, 자신의 바로 왼쪽의 탑이 자신보다 크면 저장 (첫 번째 탑이면 0 저장)
3. 자신보다 작다면, 하나 더 왼쪽을 보는게 아니라, 그 탑의 정보에 있는 탑과 비교
   (왜냐면 적어도 그 탑보다는 크다는 점이 보장되니까)
4. 그래서 그 탑도 작다면 다시 또 그 탑의 정보에 저장된 탑과 비교 … 반복

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <string>
using namespace std;

int towers[500'001] = {};
int recieve[500'001] = {};
int N;
string answer = "";

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    
    for (int i = 1; i <= N; ++i)
    {
        cin >> towers[i];
        if (i == 0) recieve[i] = 0;
        else
        {
            if (towers[i-1] > towers[i]) recieve[i] = i-1;
            else
            {
                int now = i-1;
                while (true)
                {
                    if (towers[recieve[now]] > towers[i])
                    {
                        recieve[i] = recieve[now];
                        break;
                    }
                    else
                    {
                        now = recieve[now];
                        if (now == 0)
                        {
                            recieve[i] = 0;
                            break;
                        }
                    }
                }
            }
        }
        answer += to_string(recieve[i]) + ' ';
    }
    
    cout << answer << '\n';
    
    return 0;
}

다시 생각해 볼 점

1. 상위권 풀이를 보니 스택을 활용했다.
   1. 스택이 비었다면 0을 저장
   2. 스택이 비지 않았다면 스택의 top을 버려가며 자신보다 큰 탑의 위치를 찾고 저장
   3. 그리고 스택에 자신의 위치를 저장
2. 그런데 결국 이게 내가 연결리스트? (이걸 연결 리스트라고 불러도 되는지 모르겠지만) 로 푼 과정과 같다.
   1. 위의 3번은 바로 왼쪽의 탑과 비교하는 부분
   2. 위의 2번은 다시 그 탑에 저장된 탑과 반복 비교하는 부분
3. 하지만 나는 계속 연결 리스트를 탐색해야 하지만, 스택은 한번 탐색을 하고 나면 정보가 정리된다는게 더 효율적으로 느껴졌다.
4. 그리고 나는 처음에 정보를 일단 저장한 후, 마지막에 다시 for문을 돌면서 출력을 했는데, 상위권 코드를 보니 그 때 그 때 바로 string answer에 추가해서 불필요한 반복을 없앴다.
5. 출력 방식만 그렇게 바꿨는데도 20등에 안착, to_string이 부하가 많이 걸릴꺼라 생각했는데, 최대 500’000번 순회하며 각각 출력하는게 더 부하가 걸리는 모양이다. (출력 횟수를 줄이는게 좋다는 걸 깨달았다.)
6. 20등에 안착하여 기분이 좋다.