[알고리즘][백준] 2493. 탑

 

문제

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

 

 

문제 아이디어 1: 처음부터 탐색

처음엔 왼쪽부터 탐색하면서 자기보다 낮은 탑을 만나면 자신의 포지션으로 업데이트하고 다음 것을 찾게 했습니다.

 

ex) 6 9 5 7 4 에서

6에 대하여 [9, 5, 7, 4] -> [9는 통과, 5는 부딪힘, 7은 통과, 4는 부딪힘] -> [0, 1, 0, 1]

9에 대하여 [5, 7, 4] -> [5는 부딪힘, 7은 부딪힘, 4는 부딪힘] -> [0, 2, 2, 2]

5에 대하여 [7, 4] -> [7은 통과, 4는 부딪힘] -> [0, 2, 2, 3]

7에 대하여 [4] -> [4는 부딪힘] -> [0, 2, 2, 4]

 

... 시간 초과가 발생했습니다. 그래서 방법을 달리 했습니다.

 

문제 아이디어 2: 스택

1. 일단 리스트를 뒤집어 줍니다.

4 7 5 9 6

 

2. 스택에 넣어줍니다.

result: []

stack: [4]

 

3. 다음 것과 비교해서 다음 것이 더 크면 빼주고 결과에 해당 index로 업데이트해줍니다. 이 때, 역정렬이니까 원래 리스트 index 기준으로 넣어줍니다.

result: [4] (원래 7은 4번째 index니까)

stack: []

 

4. 비교 끝났으면 현재 것을 스택에 넣어줍니다.

result: [4]

stack: [7]

 

 

반응형

 

 

N = int(input())
towers = list(map(int, input().split(' ')))
result = [0 for _ in range(N)]
# [인덱스, 높이]
stack = []

# towers.reverse() --> void
# reversed(towers) --> iterator
# towers = towsers[::-1]
towers.reverse()
for idx in range(len(towers)):
    curr = towers[idx]
    if not stack:
        stack.append([idx, curr])
    else:
        while stack:
            top = stack[-1]
            if top[1] < curr:
                result[top[0]] = len(towers) - idx
                stack.pop()
            else:
                break

        stack.append([idx, curr]) 
    # print('result:', result)

print(' '.join(str(e) for e in reversed(result)))

 

리스트 뒤집기

towers.reverse(): List의 내장 함수이며, void 값으로 리스트를 뒤집어줍니다.
reversed(towers): iterator이며, for문으로 순회 가능합니다. iterator를 반환해줍니다.
towers[::-1]: List를 반환해줍니다.