파이썬 알고리즘 164번 | [백준 2493번] 탑 - STACK

Yunny.Log ·2022년 6월 2일

Algorithm

목록 보기

167/318

164. 탑

1) 어떤 전략(알고리즘)으로 해결?

STACK

2) 코딩 설명

0105 version
옛날 version

<내 풀이>

0105 version

import sys

n = int(sys.stdin.readline().rstrip())
top = list(map(int, sys.stdin.readline().rstrip().split()))
stk = []
laser = [-1 for _ in range(n)]
for i in range(n-1, -1, -1) : 
    while stk and stk[-1][1]<top[i] :
        top_num, top_height = stk.pop()
        laser[top_num] = i 
        # number 건물의 레이저가 닿는 것은 i번 건물
    stk.append((i,top[i])) # 인덱스, 건물 높이

for l in laser :
    # 건물번호는 1번부터 시작이므로 1씩 더해줘서 출력 
    if l!=-1 : 
        print(l+1, end=" ")
    else : 
        print(0)

https://ywtechit.tistory.com/204

옛날 version


# 성공 코드
n = int(input())
top = list(map(int, input().split()))
stack = []
answer = [0 for i in range(n)]
 
for i in range(n):
    while stack:
        if stack[-1][1] > top[i]:
            answer[i] = stack[-1][0] + 1
            break
        else:
            stack.pop()
    stack.append([i, top[i]])

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

<내 틀렸던 풀이>


from re import L
import sys

n=int(sys.stdin.readline())
inp=list(sys.stdin.readline().rstrip().split())

withIndex=[]
for i in range(n) :
    withIndex.append([int(inp[i]), i+1]) #높이, 몇번째 탑인지 번호 저장
#print(withIndex)
res=[]
stk=[]
for i in range(n) :
    #print(stk)

    if stk :
        #만약 스택에 들어있는 높이 중 최댓값이 내 높이보다 작다? 
        # 그럼 내가 보낸 레이전 아무도 못받어 
        if max(stk)[0] < withIndex[i][0] :
            res.append(0) 
        
        #스택 애들 중 나보다 큰 아이 중 최신 아이
        #최신 아이 찾아야 되니깐 맨 뒤부터 검사 (역순)
        else : 
            for j in range(len(stk)-1,-1,-1) :
                if stk[j][0]>withIndex[i][0] :
                    res.append(stk[j][1])
                    break
    else :  #맨 첫번째 아이
        res.append(0)
    stk.append(withIndex[i])
    #print("res" ,res)

for i in res:
    print(i, end=" ")