[백준] 2493 : 탑

문제

막힌 부분

stack을 빈 리스트로 두고 스택에 값이 존재하지 않을 때와 존재할 때로 나눈 다음, 존재하지 않을 때는 [인덱스, 탑의 원소] 리스트를 스택으로 넣어주고 스택에 값이 존재할 때는 스택의 마지막 값과 현재 탑의 원소 크기를 비교해주는 부분을 생각하지 못했다.

스택에 들어간 마지막 값이 현재 탑의 높이보다 작을 때는 기준점으로서 스택에서 쓸모가 없어진 것이므로 stack.pop()을 해주고

스택에 들어간 마지막 값이 현재 탑의 높이보다 클 때는 수신할 수 있는 것이고 기준점으로서 쓸모가 있는 것이므로 answer를 업데이트해주고 그대로 stack도 놔둔다.

구조

1. 탑의 개수만큼 for문을 돎
2. 빈 스택을 먼저 for문 바깥에 선언해주고,
   2-1. for문 안에 스택이 존재하지 않을 때는 수신받을 수 있는 탑이 없는 것이므로 while문을 돌지 않고 스택에 인덱스 i와 해당 원소값 리스트를 넣어줌 (스택은 이차원 배열 - 인덱스 i, 해당 원소값)
   2-2-1. for문 안에 스택이 존재할 때에는 스택에 들어간 마지막 값 > 현재 탑의 높이이면 자신보다 높은 탑이 있는 것이므로 결과값에 스택의 인덱스 + 1을 추가해줌
   2-2-2. 스택에 들어간 마지막 값 < 현재 탑의 높이라면 스택에 있는 값을 pop() 해줌

기존에 답변 배열을 탑의 개수인 n개만큼 0으로 초기화해두면 따로 수신 받을 탑이 없는 경우엔 그냥 0으로 유지가 됨!

https://ywtechit.tistory.com/204

시간초과 풀이 1.

import sys
N = int(sys.stdin.readline())
t = list(map(int, sys.stdin.readline().split()))

result = []

for i in range(N-1, -1, -1):
    count = 0
    for j in range(i-1, -1, -1):
        if t[i] <= t[j]:
            result.append(str(j+1))
            count += 1
            break
    if count == 0:
        result.append("0")

print(" ".join(result[::-1]))

시간초과 풀이 2.

import sys

N = int(sys.stdin.readline())
s = list(map(int, sys.stdin.readline().split()))

res = ['0']
for i in range(1, N):
    stack = s[0:i][::-1] # 해당 원소 전까지 그리고 역순을 취해줌 
    j = 0
    while j < len(stack):
        if s[i] > stack[j]:
            stack.pop()
        else:
            res.append(str(s.index(stack[j]) + 1))
            break
        j += 1
    if len(stack) == 0:
        res.append(str(0))
        
print(" ".join(res))

정답풀이

import sys

N = int(sys.stdin.readline())
top = list(map(int, sys.stdin.readline().split()))
answer = [0 for _ in range(N)] # 아무 액션도 일어나지 않았을 때 이미 0으로 초기화되어 있음
stack = []

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]]) # 스택에 값이 존재하지 않을 때 이차원 배열로 스택에 인덱스 값과 원소값을 넣어줌

print(*answer)

22.05.16 다시 풀어보기

스스로 푼 풀이

가장 중요한 핵심 아이디어는 스택엔 항상 비교될 수 있는 최신의 기준값들을 넣어주고 더 이상 기준으로서 역할을 하지 못하면 pop() 해주는 방식을 쓴다는 것이다.

내 풀이

# 2493번 탑
import sys
input = sys.stdin.readline

def sol():
    n = int(input())
    tap = list(map(int, input().split()))

    answer = [0 for _ in range(n)] # 답안이 들어가는 리스트
    stack = [] # 레이저를 수신받은 탑의 위치(인덱스)

    for i in range(n):
        while stack and tap[stack[-1]] < tap[i]:
            stack.pop()
        
        if stack: # while문 마치고도 스택에 남아있으면 -> tap[i]보다 큰 값
            answer[i] = stack[-1] + 1
        
        stack.append(i) # 현재 탑의 index를 stack에 저장해줘야 함

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

sol()

stack에 탑의 인덱스를 넣어주는 방법

# 2493번 탑
import sys
input = sys.stdin.readline

def sol():
    n = int(input())
    tap = list(map(int, input().split()))

    answer = [0 for _ in range(n)] # 답안이 들어가는 리스트
    stack = [] # 레이저를 수신받은 탑의 위치(인덱스)

    for i in range(n):
        while stack and tap[stack[-1]] < tap[i]:
            stack.pop()
        
        if stack: # while문 마치고도 스택에 남아있으면 -> tap[i]보다 큰 값
            answer[i] = stack[-1] + 1
        
        stack.append(i) # 현재 탑의 index를 stack에 저장해줘야 함

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

sol()