BOJ 2493 - 탑

folder_open Algorithm / BOJ / gold | date_range last modified at / created at 12 Oct 2024

sell #BOJ #2493 #gold #python #파이썬 #코딩테스트 #알고리즘

맨 위로

• 문제 링크
• 잡담
• 구현
• 코드

문제 링크

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

잡담

초반에 좀 많이 헤맸다. 당장 안풀릴 때는 나중에 푸는 게 확실히 나은 것 같다.

구현

먼저 시간복잡도를 계산해보자. 문제에 $N \le 50$ 이라고 명시되어있다. 즉,

• $O(N): 500,000$
• $O(Nlog{N}): Nlog{N} \thickapprox 500,000 \times 19 \thickapprox 9,500,000$
• $O(N^2): N^2 = 250,000,000,000$
  $O(N^2)$이상으로 가면 시간초과가 날 것이다.

문제를 보면 가장 먼저 만나는 탑의 위치를 출력한다고 되어있다. 즉, 만나는 탑보다 높이가 작은 앞의 탑들은, 신경 쓸 필요가 없다. 예를 들어,

10 6 5 4 3 2 7 5 9 의 탑이 있을 때, 7을 기준으로 보면 6 ~ 2의 탑들은 신경 쓸 필요가 없다는 뜻이다. 이 다음부터는 구현이 쉽다.

코드

from sys import stdin
input = stdin.readline

def main():
    n = int(input())
    tower = list(map(int, input().split()))
    stack = []
    idx = 0
    value = 1
    for i in range(n):
        if stack:
            if tower[i] < stack[-1][value]:
                print(stack[-1][idx], end=' ')
            else:
                while stack and stack[-1][value] < tower[i]:
                    stack.pop()
                if stack:
                    print(stack[-1][idx], end=' ')
                else:
                    print(0, end=' ')
        else:
            print(0, end=' ')
        stack.append((i + 1, tower[i]))

if __name__ == '__main__':
    main()