백준 2493번: 탑

문제

• https://www.acmicpc.net/problem/2493
• 스택을 활용해 탐색 범위 줄이기 (계속 탐색할 필요성이 있는 값만 남기기)

기록 포인트

• 스택을 활용해 탐색 범위를 줄일 수 있는 상황 기억하기
  • 반복의 다음 회차에서 탐색할 필요성이 있는 값만 남겨 불필요한 탐색 횟수를 줄임

접근 방식

주먹구구의 해

• 전체 경우의 수 탐색
  • 탐색 횟수 최대 N^2
• [코드 구성]
  • 정렬되어 있지 않은 N개의 수(i) 각각에 대해
    • 본인보다 앞에 있는 수(j)들을 하나씩 역순으로 확인
      • 본인보다 큰 값을 발견하면 위치 저장 후 탐색 종료
      • 본인보다 큰 값이 없으면 없음 표시 후 탐색 종료
    • 다음 i로 이동

스택 활용

• 스택에는 반복의 다음 회차에 탐색할 필요성이 있는 값만 남김
• [코드 구성 1차]
  • 정렬되어 있지 않은 N개의 수(i) 각각에 대해
    • 본인보다 앞에 있는 수(j)를 하나씩 역순으로 확인
      • 이 때, 본인의 다음의 숫자가 고려할 숫자만 남김
      • 즉, 자신보다 큰 값만 남김
      • 자신보다 작은 값은 어차피 자신에게 걸릴 것이기 때문에 고려할 필요가 없음
• [코드 구성 2차]
  • 스택 생성
    • 스택에는 자신의 다음 숫자가 고려할 숫자만 남기도록 함
  • 정렬되어 있지 않은 N개의 수(i) 각각에 대해
    • 스택에 담겨 있는 숫자(j)들을 하나씩 확인
      • 스택에 남은 숫자가 없으면
        • 본인보다 큰 값이 없으므로, 없음으로 위치 저장
        • 스택 탐색 종료
      • 스택에 남은 숫자가 있으면 (후입선출이므로, 본인 직전의 숫자부터 확인)
        • 인출한 숫자가 자신보다 작은 경우,
          • 다음 숫자가 고려할 필요가 없으므로 제거
        • 인출한 숫자가 자신보다 큰 경우,
          • 본인보다 큰 값을 찾았으므로, 해당 위치 저장
          • 다음 숫자가 고려해야 하므로 다시 추가
          • 스택 탐색 종료
    • 다음 숫자가 본인을 고려해야 하므로, 스택에 본인 추가
      • 이 때, 본인의 위치 정보를 함께 저장
    • 다음 숫자(i)로 이동

제출 답안

import sys
N = int(sys.stdin.readline())
towers = list(map(int, sys.stdin.readline().split()))

answers = []
stack = []
for idx, t in enumerate(towers):
    ans = -1
    while True:
        if len(stack) == 0:            
            break
        prev, prev_idx = stack.pop()
        if prev > t:
            ans = prev_idx
            stack.append((prev, prev_idx))
            break    
    stack.append((t, idx))
    answers.append(ans+1)    

print(" ".join((str(n) for n in answers)))