[백준] 2493번 탑 - python 파이썬

문제

 

 

이 문제는 단순히 구현을 하는 것 보다도 어떻게 최적화된 방식으로 구현을 하느냐가 중요한 것 같다

 

처음에 단순구현한 코드는 시간초과가 발생했다

 

단순구현한 코드

n = int(input())
tops = list(map(int,input().split()))

answer = [0] * n


def find(i,tops):
    for j in range(i-1,0,-1):
        #i보다 높이가 높아서 신호를 받은 탑이 있다면 리턴
        if tops[j] >= tops[i]:
            print(tops[j],tops[i])
            return j+1
    return 0


for i in range(n):
    answer[i] = find(i,tops)

for i in range(n):
    print(answer[i]," ", end='')

 

 

 

 

이 문제를 해결해주기 위해서는 stack을 사용해주면 된다.

앞에서 부터 stack에서 이전의 탑들을 저장해주어 비교하고 빼고 하는 방식으로 해주면된다

 

 

 

정답코드

n = int(input())
tops = list(map(int,input().split()))

answer = [0] * n
stack = []
for i in range(n):
    #지금까지 담긴 stack에서 현재 탑이 쏜 레이저를 맞는 탑 찾기
    while(stack):
        #현재의 탑보다 높이가 더 높은 탑을 만나는 순간
        if stack[-1][0]>= tops[i]:
            #답에 기록하고 while문 brak
            answer[i] = stack[-1][1]
            break
        else:
            #현재의 탑 이후에 오는 탑은 현재의 탑보다 작은 탑들에게 신호를 보내줄 수 없으므로 제거
            stack.pop()

    #다음 탑을 검사하기 전 이전의 탑들만 stack에 담아주면 됨
    stack.append([tops[i],i+1])

print(*answer)

 

 

 

여기서 가장 중요한 부분은 현재의 탑 이전의 탑만 비교할 수 있도록 for문의 마지막에서 stack에 추가해주고 

현재의 탑보다 작은 탑들은 이후에 오는 탑이랑 신호를 주고받을 수 없으므로 stack.pop() 을 해주어야 한다는 점이다.