[BOJ] Q2493 탑

[BOJ] Q2493 탑

Question

Language: Python

Difficulty: Gold 5

Solution 1

stack을 활용하는 방식

현재 탑이 이전에 저장된 탑 보다 크기 작을 때까지 스택에서 저장된 탑들을 pop을 반복하고 top보다 작은 경우가 발생하였을 때 해당 top의 index값을 정답에 추가한다.

만약, stack이 비는 경우는 현재 탑이 가장 크기가 큰 것이므로 수신할 수 있는 레이더가 없기 때문에 정답에 0을 추가한다.

그런 다음, 마지막으로 해당 탑의 정보를 stack에 추가한다.

def solution():
    stack=[]
    results=[]
    for index,height in enumerate(towers):
        while stack:
            if stack[-1][0] <= height:
                stack.pop()
            else:
                results.append(stack[-1][1])
                break
         
        if len(stack)==0:
            results.append(0)
            
        stack.append((height,index+1))

    print(*results)

if __name__ == "__main__":
    n=int(input())
    towers=list(map(int,input().split()))

    solution()

Solution 2

그리디 방식을 활용하여 문제를 풀이를 하였다.

이전 탑보다 큰 탑 이면서, 기존의 최대 탑의 크기보다 큰 경우

최대 크기를 갱신하고, previous_index 값을 -1로 설정하여 해당 탑을 기준으로 왼쪽으로 더 이상 검사를 진행하지 않도록 제한한다. 그리고, 가장 큰 크기의 탑이되므로 수신 되는 탑은 존재하지 않으므로 0을 추가한다.

max_high=towers[i]
previous_indexes[i]=-1
results.append(0)

이전 탑보다 큰 탑 이면서, 기존의 최대 탑의 크기보다 작은 경우

이전 탑의 최대 크기를 비교해서 현재 탑의 크기가 큰 경우, 그 이전의 최대 크기를 비교하는 작업을 반복적으로 진행한다. 그렇게 해서 이전 최대 크기보다 작은 경우가 발생하면 해당 인덱스 값을 정답에 추가한다.

이전 탑보다 큰 탑인 경우

공통적으로 이전 최대 크기는 현재 크기로 갱신된다.

이전 탑보다 작은 탑인 경우

이전 탑에 대해서 previous_index을 기존에 저장된 previous_high_index으로 등록하고, previous_high, previous_high_index을 현재 탑의 정보로 갱신한다.

def solution():
    previous_high=towers[0]
    max_high=towers[0]
    previous_high_index=0
    previous_indexes=[-1] * n

    results=[0]
    for i in range(1,n):
        #이전 탑보다 큰 경우
        if towers[i] > towers[i-1]:
            #기존의 최대 높이보다 큰 경우, 최대높이와 이전 최대 높이를 갱신한다.
            if towers[i]>=max_high:
                max_high=towers[i]
                previous_indexes[i]=-1
                results.append(0)
            else:
                index=previous_high_index
                while True:
                    #이전 최대 높이가 높은 경우, 그 이전의 최대 높이를 찾을때까지 반복문을 수행해서 해당 인덱스를 previous_index으로 설정
                    if towers[i] > towers[index]:
                        index=previous_indexes[index]
                    else:
                        break
                previous_indexes[i]=index
                results.append(index+1)
            #기존의 탑보다 현재의 탑이 크기 때문에 이전 최대 크기는 현재의 탑으로 갱신된다.
            previous_high_index,previous_high=i,towers[i]
        #이전 탑보다 작은 경우에는, 이전 최대 크기를 이전 탑의 크기로 설정하고, 그 이전의 최고 크기와 연결해준다.
        else:
            previous_indexes[i]=previous_high_index
            previous_high_index,previous_high=i,towers[i]
            results.append(i) 

    print(*results)

if __name__ == "__main__":
    n=int(input())
    towers=list(map(int,input().split()))

    solution()