탑 - 2493번

문제

...일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

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

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

입력
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력
첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

풀이

시간초과

아래의 답안은 맞는 결과값을 출력해내기는 하나, 시간초과로 오답처리 된 코드이다.
기본적으로 이는 for문을 통해 오른쪽으로 이동하면서 하나씩 탑을 볼 때 자신이 수신될 수 있는 탑의 위치를 찾을 때 이전의 탑의 높이가 현재 탑의 높이보다 작다면 버리면 되는 논리이다.

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

towerstack = []
for i in range(N):
    towerstack.append([i, tower[i]])

answer = ''

for i in range(N):
    stack = towerstack.copy()[:i]
    if i==0:
        answer += str(0)+' '
    else:
        while stack:
            if stack[-1][1] > tower[i]:
                answer += str(stack[-1][0]+1)+' '
                break
            else:
                stack.pop()
            if not stack:
                answer += str(0)+' '

print(answer)

메모리 초과 날까봐 변수 answer를 스트링 타입으로 했는데도, 시간 초과의 벽은 못 넘은 답안이다.

위 코드를 설명하자면 반복문 밖에서, for문 돌 때마다 필요한 비교군만큼만 갱신될 변수 towerstack을 먼저 선언하였다. 반복문 시작마다 stack = towerstack.copy()[:i]을 통해 tower[i]의 왼쪽에 위치한 탑의 데이터들만 가져온다.

i==0이면 무조건 answer에 0 넣고 끝낸다.
i==1부터 tower[i]의 왼쪽에 있는 탑들인 towerstack의 맨 끝 ([-1])요소부터, 즉 tower[i]의 바로 직전에 있는 요소부터 맨 왼쪽 요소까지 순차적으로 if문으로 조건에 맞는가를 확인한다.

--> 조건문에 안 맞으면?
towerstack으로 부터 tower[i]의 바로 직전 요소 제거하여 갱신된 towerstack의 맨끝 요소와 tower[i]를 다시 비교.

--> 조건문에 부합하면?
answer에 해당 인덱스+1을 담고 그대로 break하여 해당 i에 대한 for문 돌기 끝, 다음 i for문 시작.

--> 만약 끝까지 주어진 towerstack 안 요소들이 모두 조건문에 안 맞아 towerstack이 깡통이 되면?
answer에 0을 넣어주면서 해당 i에 대한 for문 돌기 끝, 다음 i for문 시작.

ㅠㅠㅠ....
이런 식으로 짜서 반례까지 다 확인해가지고 행복했는데 시간 초과란다 내도 힘들다...

그래서 for문 안!에!서!
stack을 계속해서 넣었다 뺐다 시키는 접근을 해야 했다.

정답

아래의 코드는 정답이다.

import sys 
input = sys.stdin.readline
N = int(input())
tower = list(map(int, input().split()))
stack = []
answer = []

for i in range(N):
    while stack:
        if stack[-1][1] > tower[i]:
            answer.append(stack[-1][0]+1)
            break
        else:
            stack.pop()
    if not stack:
        answer.append(0)
    stack.append([i, tower[i]])

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

탑 높이값의 리스트 tower를 반복문 돌리면서, 담기용 변수 stack에 비교대상이 되는 탑들을 계속 넣어가며 높이 차이의 여부를 체크한다.

비교적 간단해보이는 문제와 달리 실제 답안을 디버깅해보면 맨 처음에가 헷갈린다...
아래를 보자.

    while stack:
        if stack[-1][1] > tower[i]:
            answer.append(stack[-1][0]+1)
            break
        else:
            stack.pop()

여기 부분의 함수의 진행이 딱 "stack에 비교 돌릴 탑 데이터를 넣는다 -> 조건문으로 거른다 -> answer에 넣거나 pop()하거나" 이 순서대로 돌질 않는 느낌을 주기 때문에 헷갈릴 수 있다....

첫번째 답안의 변수 towerstack은 for문 돌 때에 이번 i회차 순회에서 필요한 비교군들을 먼저 싹 가져온 다음 if문을 돌기 시작하는 반면,

이 답안에서의 변수 stack은 이번 i-1회차 순회 때 stack에 넣어놓았던 비교군으로 현재 tower[i]와 비교한다. 그래서 조건 안 맞으면 바로 팝하고, "너 깡통? 응, answer에 0 어펜드. 넘어감." 한 뒤 for문의 문을 닫으면서 stack.append([i, tower[i]])를 하는 것....