https://www.acmicpc.net/problem/2493
공부 날짜 : 2023.01.19
정답 참조 여부 : X
높이가 서로 다른 기둥에서 레이저가 발사될때 레이저가 부딪히는 기둥을 구하는 문제이다.
(설명은 조금 다르지만, 비슷한 의미로 해석될거 같습니다.)
처음에는 자신의 위치를 기준으로 왼쪽으로 index를 1씩 줄여가며 자신보다 높은 기둥을 찾았다.
결과는 시간초과 Pypy3로도 시간초과가 나왔다.
방법을 좀 더 생각해봤는데
A기둥과 비교해서 높이가 낮으면 A기둥의 레이저가 부딪히는 기둥 B와 높이를 비교하는 식으로 반복하다가, 높이가 높은 기둥을 찾으면 저장하고 A기둥이 다른 기둥에 부딪히지 않으면 지금 기둥도 부딪히지 않는걸로 처리했다.
설명을 글로써서 내가봐도 모르겠긴 하다.... 다음번에 봤을 때 이해할 수 있을지 모르겠는데
문제를 풀고나서 dp의 풀이방법 아닌가? 싶긴 했는데 알고리즘을 확인하니 그냥 스택 자료구조를 사용한다고 한다.
소스코드
import sys
input = sys.stdin.readline
################################################
n = int(input())
input_data = list(map(int, input().split()))
answer = [-1] * n
# 2번째 기둥부터 체크
for i in range(1, n):
index = i - 1
while True:
# 지금 체크하는 기둥이 나보다 크면 저장 후 멈춤
if input_data[index] > input_data[i]:
answer[i] = index
break
# 작으면
else:
# 해당 기둥이 수신된 기둥 체크
# 만약 없으면 0 입력후 멈춤
if answer[index] == -1:
answer[i] = -1
break
# 그 작은 기둥이 인식된 기둥과 비교
index = int(answer[index])
for num in answer:
print(num+1, end = " ")
