2493번 - 탑

💡 조금 더 열심히 공부해야겟다..ㅎ

# 시간제한이 1.5초이기 때문에, for문은 1번만 사용하기 ( 스택, 투포인터는 정렬필요하니 제외)

import sys

input = sys.stdin.readline

N = int(input())

tower = list(map(int, input().split(' ')))
position = [0] * N
stack = []

for i in range(N):
    
    while stack:
        if tower[i] > tower[stack[-1]]:
            stack.pop()
        else:
            position[i] = stack[-1] + 1
            break
    
    stack.append(i)
    
print(*position)

• 정말 나한테는 너무 어려운 문제였디..ㅎ
• 우선 시간복잡도를 분석하였을 때, 1.5초이고 N의 최댓값이 500,000이였기 때문에 2중 for문을 사용하면 시간초과가 발생할 것이라고 생각하였다.
• 그래서 투포인터나 2개의 스택을 사용해서 풀어보려고 노력하였지만, 결국 생각이 나지 않아서 정답을 참고하여서 깨우쳤다.

💡 풀이방법

1. stack에는 현재의 index값이 1번씩 push 되어진다. ( 왼쪽 -> 오른쪽)
2. push되기 전에 stack이 비어있지 않으면, stack의 마지막 원소와 현재 타워 높이를 비교한다.
   => stack의 마지막 원소가 현재 타워 보다 작으면, stack의 마지막 원소를 pop()한다. (stack이 빌때까지 반복)
   => stack의 마지막 원소가 현재 타워보다 크면, 해당 position에 현재 인덱스 값을 넣고 while문을 빠져 나간다.
3. 현재 index값을 스택에 추가한다.

• 문제상 오른쪽에서 왼쪽으로 이동하면서, 현재 타워보다 큰 타워에만 전송할 수 있으니, 왼쪽에서 오른쪽으로 가면서, 현재 본인의 높이와 이전 타워의 높이를 비교한다.
• 결국은 본인보다 큰 가장 가까원 원소의 index를 찾아야하기 때문에, 결국은 본인보다 작은 높이를 가진 탑의 인덱스를 계속 지워가면서 본인 보다 큰 가장 가까운 인덱스를 찾는 방식으로 진행하였다.

+) for문 내부에 while문이 들어가면 결국은 최악의 상황때, O(N^2) 되는거 아니야?
=> stack을 사용했기 때문에 각 요소당 push도 1번, pop도 1번씩 일어나기 떄문에,
최악의 상황에도 2N만 돌기 때문에 O(N)이다.