[백준 2493번] 탑

n = int(input())

tops = list(map(int,input().split()))

answer = [0 for _ in range(n)]

stack = []

for i,value in enumerate(tops):
    while stack:
        if stack[-1][1] <= value:
            stack.pop()
        else:
            answer[i] = stack[-1][0]
            break
    if len(stack) == 0:
        answer[i] = 0
    stack.append((i+1,value))
            
print(' '.join(str(s) for s in answer))

이번 문제는 탑들의 높이가 주어졌을 때, 왼쪽 방향으로 레이저 신호를 날렸을 때 수신한 탑들의 번호를 구하는 문제이다.
 
처음에 이 문제를 최대한 효율적으로 풀어보려고 했지만(max_value를 설정), 결국 2중 반복문을 사용하게 되어 O(N^2)의 시간복잡도를 가지게 되고, 최악의 경우 500,000 * 500,000 = 250,000,000,000 의 연산으로 인해 시간 초과가 발생하게 되었다.
 
결국 O(N)이나 O(N logN)의 시간복잡도로 해결해야 하는데, 머리 속으로는 풀이가 생각날 듯 했지만 구현이 잘 되지 않아 다른 분의 풀이를 참고하였다.
 
결국 이 문제는 'Stack 자료구조'를 사용하여 각 원소가 스택에 들어가고 나오는 연산이 한 번씩만 수행되는 O(N) 시간복잡도로 해결해야 한다는 것이다.
 
하지만 결국 for문과 while문을 2중으로 사용한다는 점 때문에 왜 O(N)인지 이해가 안갔는데, 다음과 같은 답변이 있었다.
 

 첫번째 코드에서 이중 반복문을 각각 최악의 경우 `O(N)`번씩 돈다고 생각해서 `for * while = O(N^2)` 이라고 판단하면 안된다. 만일 바깥 루프가 한번 돌 때 운이 안 좋아서 안쪽 루프의 `N`개의 원소를 pop했다고 가정하면, 그 한번의 루프를 제외한 나머지는 모두 `pop`을 안했다는 것이다.(while stack: 조건때문에) 즉, 아무리 루프를 오래 돌리려고 해도 안쪽 루프가 N번보다 많이 돌 수 는 없다. 언젠가 많이 돈 때가 있다면, 다른 때는 많이 안 돌았어야만 하고 총 횟수 역시  `O(N)`밖에 안된다. 즉, 안쪽 루프가 도는 총 횟수를 다 합했을 때 `O(N)`이라는 큰 그림을 보는게 중요하지, 바깥 루프가 한 번 돌때 안쪽 루프가 최대 `O(N)`번 도는 그림은 볼 필요가 없다는 뜻이다. 이 코드의 최악의 경우에도 전체가 `O(N)`이다. "

 
정리하자면, 빈 스택(리스트)을 선언한 후 왼쪽부터 값을 삽입하면서 더이상 수신가능 여부를 확인할 의미가 없는 탑들은 제거(pop)하는 방식으로 푸는 것이다. 그렇게 되면 각 원소들마다 N번씩 확인할 필요가 없기 때문에 내부 loop가 N번보다 많이 돌 수 없게 되고, 최종적으로 O(N)으로 풀이할 수 있게 된다.
 

배운 점 및 느낀 점

1. 자료구조 개념이 많이 부족하다고 느껴지던 것이 좀 더 체감이 되었다. 기본적인 자료구조에 충실해지기 위해 더 공부하자.
2. 항상 시간복잡도를 먼저 계산해본 뒤에 문제풀이에 들어가도록 하자.
3. 잘 풀리지 않는다면 불필요한 연산을 줄이기 위해서 어떤 자료구조를 사용할 수 있는지 고민해보자.
4. " ".join 함수로 배열을 문자열로 변환시킬 수 있는데, 이때 배열의 원소들이 문자열이여야 하므로 정수형이라면 for 문으로 변환시켜주도록 하자