[백준/python] 2493 탑

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

2493번: 탑

 

• 사용언어 : python
• 알고리즘 : 자료 구조, 스택
• Solved.ac Tier : Gold V

 

python 코드

1. 문제 정리

이 문제는 시간이 1.5초이고 주어지는 탑의 개수가 50만개이기 때문에 시간 복잡도가 O(N^2)를 넘어서면 시간 초과가 발생 한다. 따라서 문제를 해결 할 때 탐색 하는 것을 빼야 했다.

import collections
import sys
from collections import deque
n = int(sys.stdin.readline().rstrip())
data = deque(map(int, sys.stdin.readline().rstrip().split()))
ans = deque()

for _ in range(n):
    cmp = data.pop()
    find = False
    for i in range(len(data), 0, -1): 
        if(cmp < data[i - 1]):
            ans.appendleft(i)
            find = True
            break
    if(not find):
        ans.appendleft(0)

print(*ans)

제일 처음에 굉장히 간단한 문제라고 인식하고 값을 하나하나 탐색하여 문제를 해결 하려고 했다. 하지만 바로 시간 초과였다.

 

따라서 다른 방식을 이용하여 문제를 해결 해야 했다. 문제의 태그가 스택이니 스택으로 무언가 해결해야 한다고 생각했다. 

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

구조는 다음과 같다.

1. 스택을 만들 때 2차원 배열 구조로 만들어 2차원 배열 안에 index와 value(탑 높이)를 모두 담는다. 

2. 스택을 처음부터 모두 채우지 말고, 하나하나 비교해가면서 채운다.

2-1. 만약 stack 안에 있는 마지막 인덱스의 탑 높이가 현재 비교하고 있는 리스트보다 크다면 ans[i]에 값을 할당 해준다.

2-2. 아니라면, stack 맨 위에 있는 값을 제거한다.

이 방식으로 계산하다보면, 무조건 list[i]값보다 큰 탑의 높이는 스택에 계속 남아 있을 것이다. 따라서 O(N^2) 시간 복잡도를 가지지 않고, 스택을 활용하여 푼 방식이다.

 

2. 완성 코드

import sys
from collections import deque
n = int(sys.stdin.readline().rstrip())
list = list(map(int, sys.stdin.readline().rstrip().split()))
stack = deque()
ans = [0 for i in range(n)]

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

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