[BOJ] 2493: 탑

이슬비·2023년 1월 24일

Algorithm

목록 보기

65/110

당분간 자료구조만 파야겠다 ...

1. 내 풀이

import sys
input = sys.stdin.readline

n = int(input())
building = list(map(int, input().split()))
result = []
for i in range(n-1, 0, -1):
    for j in range(i-1, 0, -1):
        if building[j] > building[i]:
            result.append(j+1)
            break
    if len(building[i:]) != len(result):
        result.append(0)
result.append(0)

for i in range(n-1, -1, -1):
    print(result[i], end=" ")

당근빠따루 ~~~ 틀림 ~~~
틀렸다기보단 시간 초과가 났다.
완전 탐색 방법을 썼기 때문이다 ...!

그 외에도 여러가지 방법을 써봤으나 시간초과 or 아예 틀린 답이 나와서
그냥 답을 보기로 했다.

2. 다른 풀이

1. 첫번째 방법

import sys
input = sys.stdin.readline

n = int(input())
t_list = list(map(int, input().split()))
result = []
stack = []

for i in range(n):
    current = t_list[i]
    if stack:
        while stack:
            if stack[-1][0] < current:
                stack.pop()
                if not stack:
                    print(0, end=" ")
            elif stack[-1][0] > current:
                print(stack[-1][1]+1, end=" ")
                break
            else:
                print(stack[-1][1]+1, end=" ")
                break
        stack.append([current, i])
    else:
        print(0, end=" ")
        stack.append([current, i])

풀이 출처: https://one-step-a-day.tistory.com/111

stack을 문제였기에 그대로 stack을 쓴 문제였다. 나는 여기서 어떻게 stack을 쓰는 게 맞는 걸까라는 생각만 들었는데 ...

더불어 나는 아예 오른쪽 (예제 기준 4부터) 부터 for문을 돌았는데 대부분의 풀이가 왼쪽으로부터 시작했다. 이 방향 설정부터 잘못되었던 것 같다. 앞으로는

문제가 너무 안 풀린다 싶으면 방향을 바꿔보자는 생각도 해보자!!!

2. 두번째 방법

import sys
n = int(sys.stdin.readline())
t_list = list(map(int, sys.stdin.readline().split()))
stack = []
goto = [0]*n

for i in range(n):
    current = t_list[i]
    while stack and t_list[stack[-1]]<current:
        stack.pop()
    if stack:
        goto[i] = stack[-1] + 1
    stack.append(i)

print(' '.join(list(map(str, goto))))