BOJ - 탑 2493번 (python)

❓ 문제 - 백준 탑 2493번 - python 풀이법

출처 

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

2493번: 탑

 

 

📝 문제해결법

1. 이 문제의 핵심은 시간복잡도를 고려하는 것이다. N의 범위가 N은 1 이상 500,000 이하이므로 O(N)으로 풀어야 한다.

2. 스택을 사용하여 해결하는 것이 특징이다.

• 스택에 맨 오른쪽 탑부터 시작하여 스택에 해당 탑의 길이와 탑의 인덱스를 넣어줌
• for문을 통해 stack의 top보다 큰 탑이 나온다면 answer 리스트의 해당 top값의 인덱스의 값을  큰 탑의 인덱스 값으로 변경
• 만약 stack에 아무 값이 없다면 break

 

 

** 풀이 참조

(https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%802493%EB%B2%88%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%ED%83%91-%EA%B7%B8%EB%A6%AC%EB%94%94-Greedy)

 

해당 블로그의 풀이법을 참조하여 공부하였습니다.

 

 

 

 

💻 소스코드

import sys

input = sys.stdin.readline
n = int(input())
data = list(map(int, input().split()))

stack = []
answer = [0] * n

for i in range(len(data)-1, -1, -1):
    if len(stack) == 0:
        stack.append([i, data[i]])
    else:
        while data[i] > stack[len(stack)-1][1]:
            top = stack.pop()
            answer[top[0]] = i+1
            if len(stack) == 0:
                break
        stack.append([i, data[i]])

for i in answer:
    print(i, end=' ')

 

 

🧐 Ellen's Thinking

이중 for문을 사용한다면 시간 복잡도는 O(N^2)이고, for문과 while문 stack을 잘 구현한다면 시간 복잡도를 O(N)으로 구현할 수 있다는 것을 깨달았다.