2493

날짜 : 2023. 07. 24

사용 언어 : python

 

문제

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

 

 

코드

import sys

n = int(sys.stdin.readline())
tower = list(map(int, sys.stdin.readline().split()))
stack = list()
stack.append((-1, -1))
res = [0] * n

# 현재 높이가 스택의 top보다 높다면 pop(반복), 낮으면 해당 인덱스 저장
for i in range(n):
    while stack:
        if tower[i] > stack[-1][0]:
            stack.pop()
        else:
            break
    if not stack:
        res[i] = 0
    else:
        res[i] = stack[-1][1]
    stack.append((tower[i], i+1))
print(*res)

 

 

풀이

- 좌측에서 우측으로 진행한다.

- (높이, 인덱스) 저장용 스택과 결과 출력용 리스트를 만들고 모든 높이에 대해 완전탐색을 실행한다.

- 현재 높이에 대하여 스택에 저장된 높이들과 비교를 진행하고, 스택의 top에 저장된 높이보다 현재 높이가 크다면 레이저를 받을 수 없기 때문에 pop을 처리, 만일 같거나 작다면 해당 인덱스를 저장하고, stack에 push한다.

- 그리고 스택에 push할 때 그 인덱스를 결과값을 출력할 리스트에 저장한다.

- 전체 루프를 다 돌고 나면 출력

 

 

알게된 점

- 우선 DP와 비슷한가 싶어서 우측에서 좌측으로 비교하면서 진행하려고 했지만 n의 최대 크기가 50만이었기 때문에 O(n^2)로는 확실히 풀 수 없는 문제였다.

- 그래서 좌 -> 우로 진행방향을 바꾸어서 문제를 풀어보려 했지만 풀이방식이 생각나지 않아 다른 사람의 풀이방향을 참고했고, 위의 코드를 도출할 수 있었다.

- 골자는 현재 높이를 기준으로 스택에 저장된 높이들을 비교하는 것이 메인이었다.

- 간단히, 약한 높이는 전부 쳐낸다고 생각하면 되고, 스택은 높이에 대하여 자연스럽게 내림차순으로 정렬된다.

 

- 만약 6 9 8 5 7의 경우에 6, 9의 경우에는 자연히 0이라는 값이 나오고, 8은 앞전에 있는 9때문에 2로 결과값을 설정한 다음 스택에 (8, 3)으로 저장된다.

- 그리고 5의 경우에는 앞의 8에게 막히기에 자연스럽게 (5, 4)로 저장되고, 마지막 7에서는 5보다 크기 때문에 top 부분이 pop되어 (8, 3)으로 최신화 -> 8에게 막혀 (7, 5)로 저장후 해당 값들이 설정된다.

- 중간값이 어떻게 되느냐를 확실하게 해결하지 못해서 꽤나 고민했던 것 같다.

 

 

 

 

참고 사이트

- https://one-step-a-day.tistory.com/111

백준 - 탑(2493) Python