탑 백준 2493번 스택

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

문제 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

---

문제 자체는 간단합니다. 예시에서 6-9-5-7-4가 있습니다.

그리고 왼쪽(들어온 순서)으로 레이저 신호가 나가는데 높이가 6인 탑은 왼쪽에 아무것도 없으니 수신을 못받고 높이가 9인 것은 수평으로 쏘는데 높이가 6번인 탑은 높이가 낮아서 수신을 받지 못합니다. 5번 탑은 9가 7번탑은 9 4번 탑은 7번 탑이 받아주게 됩니다.

loop = int(input())
top_list = list(map(int,input().split()))
from collections import deque
top_index = deque()
for i in range(loop-1,-1,-1):
    check = len(top_index)
    for j in range(i-1,-1,-1):
        if top_list[i]<=top_list[j]:
            top_index.appendleft(j+1)
            break
    if check == len(top_index):
        top_index.appendleft(0)
print(list(top_index))

일단 앞에서 탐색하기 보다 뒤에서 보는게 좋겠다는 생각을 했습니다. 예시로 나온 숫자를 가지고 잠깐만 생각을 해보면 훨씬 복잡하거든요

뒤에서 부터 하나씩 내려가면서 보게되고 이는 range에다가 스탭을 -1로 하면 역순으로 출력을 할 수 있습니다.

처음 시작을 5라고 했을때 인덱스 기준 4-3-2-1을 보게 되고 그안에 있는 루프 문은 당연히 3-2-1 순으로 돌게 됩니다.

그리고 이때 조건을 만족하는 탑을 만나게 되면 탑의 인덱스를 추가 하고 빠져나오고 만약 탑을 찾지 못했다는 것은 top_index에 아무것도 추가를 하지 못했기에 길이가 같은 경우로 보고 0을 추가 했습니다. 여기서 list가 아니라 deque 자료형을 사용한 이유는 뒤에서 부터 보기 때문에 list의 append를 사용해서 추가할경우 마지막에 한번 뒤집어 줘야하는데 deque는 왼쪽부터 삽입하는 것이 가능해서 뒤집지 않고 마지막에 list로 자료형만 변경하면 됩니다.

결과는 시간 초과

모든 공간을 탐색하는 것도 아니고 일정 조건을 만족하면 빠져나오기 때문에 괜찮을 것이라고 생각했으나 결국 O(n^2)의 완전 탐색과 같은 시간복잡도를 가지기에 안되나 봅니다.

문제의 분류는 스택으로 되어 있습니다. 그러니 스택을 사용한 아이디어로 문제를 다시 접근해봅시다.

스택에서 관리 되어야 할 것은 우리가 볼 수 있는 제일 높은 탑은 어디인가?

예시에서 마지막 4를 뺀 [6,9,5,7]을 두고 가정을 해봅시다. 9와 7사이에 5가 들어 있지만 해당 값은 7이후에 5보다 작은 4가 오든 9보다 큰 10이 오든 영향을 주지 못하는 숫자 입니다. 결국 7이나 9에서 답을 찾거나 아니면 0을 반환하게 됩니다. 이를 생각해서 다시 한번 코드를 짜봅시다.

num = int(input())
top_list = list(map(int,input().split()))

top_stack = []
answer = []

for i in range(num):
    while top_stack:
        if top_stack[-1][1] >= top_list[i]:
            answer.append(top_stack[-1][0]+1)
            break
        else:
            top_stack.pop()
    if not top_stack:
        answer.append(0)
    top_stack.append([i, top_list[i]])

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

먼저 top_stack로 스택을 관리합니다. 그리고 리스트의 첫번째 6과 인덱스 0을 넣습니다.

그다음 9가 들어 왔습니다. 스택에 있는 숫자가 9보다 큰지 확인을 하는데 큰게 없습니다. 스택에서 제거 합니다. 그러면 결국 if not 스택 스택에 들어 있는 값이 없기에 0을 삽입합니다. 그리고 마지막에 숫자 9와 인덱스 1을 넣습니다. 이대로 반복을 합니다.

그러면 5의 경우 9가 있으니 값을 추가하고 5를 넣어 줍니다. 7이 들어올때는 5를 빼고 인덱스 값을 넣고 7을 넣어주게 되고 마지막 4까지 가게 됩니다.

천천히 코드를 보시면서 print로 찍어보면 이해가 되실 겁니다.

답지 안보고 푼다고 오늘은 이거 하나 풀었네요, 그래도 고민하는 만큼 더 성장 할 수 있을거라 믿어야지