[백준] 2493 탑

 

2493번: 탑

 

 

골드 5는 항상 쉬워보이지만 풀다보면 어려운 것.. 

 

처음에 제출한 코드는 시간초과가 났다. 

 

 

<첫번째 코드 - 시간초과>

#2493 탑, 첫번째 시도 시간초과

n=int(input())
arr=list(map(int,input().split(" ")))
candi=[] #후보리스트

answer=[0]

for i in range(1,n):
    candi=[]
    for j in range(i-1,0,-1):
        if arr[j]>arr[i]:
            candi.append(j+1)
            break
    if len(candi)==0:
        answer.append(0)
    else:
        answer.append(candi[0])

print(" ".join(map(str,answer)))

 

1. 일단 처음에 있는 탑은 왼쪽에 아무 탑도 없으니 그냥 0을 먼저 넣어줬다. 

2. 그리고 for문을 현재 탑 왼쪽에서 1번 탑까지 거꾸로 돌면서 현재 탑의 높이보다 큰 높이를 가진 탑이 있으면 candi 리스트에 넣고 break

3. 후보리스트 길이가 0이면 answer 리스트에 0을 넣고 후보 리스트 길이가 0이 아니면 candi 리스트에 최초로 넣었던 탑의 인덱스를 넣었다. 

 

결과는 맞게 나왔으나 시간초과가 걸린... 

 

 

<두번째 코드 - 맞음>

 

현재 탑의 높이보다 높은 탑 중 가장 가까운 탑의 인덱스+1 을 저장하는 방법을 사용했으나 현재 탑보다 높은 탑이 없을 경우 왼쪽에 있는 탑 전부를 확인 해야하는 것이 시간초과를 나게 한 주범인 것 같다...  

이를 방지하기 위해 필요없는 값들은 보지 않게 하는 게 중요한데,,, 이걸 어떻게 해야 할지 도저히 생각이 안나서 구글링을 해봤다.

#2493 탑, 두번째 시도 stack 이용. 

n=int(input())
arr=list(map(int,input().split(" ")))
candi=[]
answer=[]

for i in range(n):
    while candi: #후보탑이 없을 때까지 돌기
        if candi[-1][1]>arr[i]:#스택 맨 위에 있는 탑의 높이 비교
            answer.append(candi[-1][0]+1) #높으니까 인덱스 저장
            break #반복문 종료
        else:
            candi.pop() #낮으면 스택에서 삭제
    if not candi:
        answer.append(0) #신호 받는 탑이 없으면 0 저장
    candi.append([i,arr[i]]) #현재 탑과 인덱스 후보에 넣어주기

print(" ".join(map(str,answer)))

 

대부분이 위의 코드를 사용했다. 스택을 사용해서 스택에 탑과 인덱스를 같이 저장하고, 스택에 맨 위에 저장된 탑의 높이가 현재 탑의 높이보다 높으면 answer에 인덱스+1을 저장하고, 낮으면 맨 위에 저장된 탑의 정보를 아예 삭제한다. 아예 삭제해도 되는 이유는 앞으로도 확인 할 일이 없기 때문이다. 이게 바로 핵심..!!  

스택에서 삭제를 한다는 뜻은 현재 확인하고 있는 탑의 크기가 왼쪽에 있던 탑들보다 더 높다는 뜻이므로 현재 탑의 높이가 오른쪽에 있는 탑의 높이보다 높다고 하면 현재 탑이 신호를 받을 것이기 때문.