[백준 -골드5] 2493번 탑(스택, 파이썬)

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

2493번: 탑

 

<복습 체크>

22/02/18
O

 

<내 코드 1>

+) 다시 풀어보니 17298번 오큰수랑 거의 유사한 문제

- 골드 문제인데 생각보다 쉽네하고 신나게 채점을 돌렸다.. 시간 초과...

- 입력받은 탑을 for문으로 뒤에서부터 역순으로 순회한다.

- 이 때 스택에 탑의 높이와 인덱스를 담아준다.

- 스택이 비어있지 않고, 스택의 가장 끝에 있는 원소보다 다음에 들어온 탑이 더 크다면

- 스택에서 pop하고 reuslt[idx]에 현재 인덱스를 넣어준다. (이때 문제에서 인덱스는 1-N이므로 주의)

- 반복문 오랜만에 거꾸로해서 실수를 했다. (n-1,0,-1) ---> (n-1, -1,-1) 이런 실수는 하지 말자...ㅎ

import sys
input= sys.stdin.readline

n = int(input())
top = list(map(int, input().split()))

stack = []
result = [0]*n
for i in range(n-1,-1,-1):
    while stack and stack[-1][0] < top[i]: #빌딩이 더 크다면
        temp, idx = stack.pop()
        result[idx] = i+1 #인덱스 넣어줌
        
    stack.append([top[i],i])
    
print(*result)

 

<내 코드 2>

- 골드 문제인데 생각보다 쉽네하고 신나게 채점을 돌렸다.. 시간 초과...

- 시간초과 코드는 pop을 통해 맨 끝부터 확인을 해주고 while문으로 앞에 자신보다 큰게 있을때까지 체크를 했다.

- 아래 코드는 맨 앞에서부터 확인을 하고 while문을 통해 앞의 탑의 높이가 다음거보다 크면 해당 인덱스를 기록해준다.

- 스택에 담을 때는 인덱스와 탑의 높이를 같이 담아준다.

import sys
input = sys.stdin.readline

n = int(input())
tower = list(map(int, input().split()))
stack=[]
answer = [0]*n
for i in range(n):
    while stack:
        if stack[-1][1]>tower[i]:
            answer[i] = stack[-1][0] +1
            break
        else:
            stack.pop()
            
    stack.append([i, tower[i]])
            
print(*answer)

 

<시간 초과 코드>

- while문이 최악의 경우 n-1까지 탐색을 하기때문에 최악의 경우 시간복잡도가 n(n-1)이 되어서 시간초과가 난것같다.

- 파이썬은 1초에 약2000만번 연산을 수행하는데, 주어진 문제에서는 N이 50만이었다,, N^2 = 2500억,,, ㅎ

import sys
input = sys.stdin.readline

n = int(input())
tower = list(map(int, input().split()))
answer = []
for _ in range(n):
    temp = tower.pop()
    if len(tower) ==0:
        answer.append(0)
        break
    i = len(tower)-1
    while True:
        if temp<tower[i]:
            answer.append(i+1)
            break
        else:
            i -=1
            if i <0:
                answer.append(0)
                break
        
for i in range(len(answer)-1,-1,-1):
    print(answer[i], end = ' ')