백준 / 골드 5 / 2493. 탑

제가 롯데월드를 가고 싶어서 롯데월드타워 사진을 올려봤습니다. 아틀란티스 타고 싶다 ㅠ

• 맨 처음엔 이중 for문으로
  • 첫 for문으로 각 탑을 순회하고
  • 두번째 for문으로 이전 탑의 높이를 체크해야지! 라고 생각하셨을 수도 있습니다.
• 그런데 이렇게 쉽게 풀리면 골드 5 문제가 아니겠죠?
• $N$의 최댓값은 $500,000$... $O(N^2)$로는 1.5초 안에 못 풉니다.
• 대신 $O(N)$ 안에 푸는 방법을 생각해봅시다.

생각해봅시다!!

• 신호는 오른쪽 -> 왼쪽으로 이동하니, 오른쪽 탑부터 역순으로 차례로 높이를 확인합니다.

  • 나중에 나온 탑과 높이를 비교하려면, 높이를 어딘가에 저장해 둬야겠죠?

• 각 탑의 신호는 자신보다 왼쪽에 있는, 제일 가까운 높은 탑에서 받게 됩니다.

  • 이때 어딘가에 최근에 저장한 탑부터 길이를 비교해야 합니다. 왜냐하면 제일 가까운 탑부터 확인해야 하니까요!!

• 최근에 확인한 것부터 확인한다?? 저장한 데이터 중 제일 최신인 데이터를 먼저 확인할 수 있는 구조가 뭐였죠?

• 바로 스택이였죠!! 스택을 이용해 풀어봅시다.

풀이

N = int(input())
heights = list(map(int, input().split()))
stack = []

# answer[idx]: idx번째 탑의 신호를 받은 탑
# 단, 신호를 받지 못하면 0
answer = [0] * (N + 1)					

for i in range(len(heights), 0, -1):
    height = heights[i - 1]
    
    # 스택 맨 위에 저장된 탑의 신호를, 현재 탑이 받는 경우
    while stack and stack[-1][1] <= height:
        answer[stack.pop()[0]] = i
      
    # 현재 탑을 스택에 추가
    stack.append((i, heights[i - 1]))   # 탑 번호, 탑 높이
    
print(*(answer[1:]))

• heights 배열을 역순으로 순회하며, 스택에 (탑 번호, 탑 높이)를 삽입합니다.
• 단 현재 탑의 높이가 스택 맨 위에 저장된 탑보다 높거나 같으면,
  • 스택 맨 위 탑이 보낸 신호는, 현재 탑이 받게 됩니다.
  • 신호를 어디에서 받았는지 확인했으니, 스택 맨 위에 저장된 탑은 스택에서 삭제해도 됩니다.
  • 따라서 스택에서 팝하고, answer 배열에 결과값을 저장해 둡니다.
  • 스택이 비었거나, 스택의 맨 위 탑이 현재 탑보다 높을 때까지 반복합니다.
    • (현재 탑이 2개 이상의 신호를 받을 수도 있으므로...)
• 이 과정을 수행한 뒤, 스택에 (탑 번호, 탑 높이)를 푸시해야 합니다.

시간 복잡도

• 탑의 수가 $N$개일 때, for문을 1회 순회하기 때문에 $O(N)$
  • 물론 스택에서 팝하는 과정에서 while문을 순회하긴 하지만, 팝은 전체 총 탑의 수인 최대 $N$번까지만 이루어지므로 시간 복잡도에 영향을 주지 않음
• 최종 $O(N)$, $N \leq 500,000$이므로 충분히 가능!

기억할 점

• 가장 최근에 조회, 저장한 데이터부터 확인할 방법이 필요하다? 스택을 떠올리자.