#2493. 탑

백준- 골드5문제이다.

📖Problems

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 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을 출력한다.

예제

input >> 5
6 9 5 7 4

output >> 0 0 2 2 4

🔍Institution

문제 정리

서로 다른 높이의 탑이 일직선으로 왼쪽에서 오른쪽으로 있다. 각 탑 위에는 레이저 송신기가 있다.
탑의 기둥에는 레이저 신호를 수신할 수 있다. 단 하나의 탑에서만 수신 가능하다.
탑 순서의 반대방향(왼쪽방향)으로 레이저 신호를 발사한다. 자신보다 더 높은 곳에 발사 가능하다.

이 문제는 스택을 사용해야 한다.

탑은 왼쪽부터 오른쪽이지만, 발사하는 방향이 탑의 반대방향으로 발사한다. 즉 연산이 뒤에서부터 수행된다. LIFO 형식이다.
단순히 생각하면 하나의 기준 탑을 잡고, 그 왼쪽을 순회하며 봐야하므로 O(N^2)으로 해결 가능하다. 하지만 문제 조건이 최대 500,000개의 탑 이므로 N^2, 혹은 N*M의 순회는 최대 250억 번의 연산을 해야한다. 이를 O(N)으로 해결해야하며, Stack을 사용한다.

🔍Approach

스택을 사용하는 것까지는 알았다. 이 문제에서는 어떤 용도로 스택을 사용할까?

스택에는 신호를 수신할 수 있는 탑을 append하고, 탑의 높이가 작은 경우 pop을 한다.

의미없는 탑은 stack에 넣지 않는다.

stack에 append할 때 index와 탑의 높이를 함께 append한다.

stack = [[i, tower[i]] → stack = [[0,6]]

그러면 index도 함께 저장이 된다.

과정

tower = [6, 9, 5, 7, 4]

1. 첫번째 탑 : 6

stack

| [0,6] | | | | | | — | — | — | — | — |

answer

| 0 | | | | | | — | — | — | — | — |

처음에 오는 탑은 6 인데, 얘는 맨 왼쪽에 있는 탑이기 때문에 그 왼쪽에 수신할 수 있는 탑이 없으므로 result에는 0이 들어가고 현재 이 친구가 가장 높은 탑이므로 stack에 들어간다.

2. 두번째 탑 : 9

stack

| [1,9] | | | | | | — | — | — | — | — |

answer

| 0 | 0 | | | | | — | — | — | — | — |

높이가 9인 탑이 들어온다. stack에 있는 높이 6인 탑과 비교했을 때 더 높으므로 stack에 있는 (0, 6) 은 pop 되고 (1, 9) 가 들어가게 된다. 마찬가지로 수신할 수 있는 탑이 없으므로 result에 0이 들어간다.

세번째 탑 : 5

stack

| [1,9] | [2,5] | | | | | — | — | — | — | — |

answer

| 0 | 0 | 2 | | | | — | — | — | — | — |

높이가 5인 탑이 들어온다. stack에 있는 높이 9인 탑과 비교했을 때 더 낮으므로 stack에 있던 (1, 9)는 유지되고 뒤에 (2, 5) 가 들어간다. 수신할 수 있는 탑이 있으므로 result에는 높이 9인 탑의 번호인 2가 들어간다. (높이가 9인 탑의 index가 1인 것이므로 탑의 번호는 index+1 해서 2가 된다.)

네번째 탑 : 7

stack

| [1,9] | [2,5] | | | | | — | — | — | — | — |

answer

| 0 | 0 | 2 | 2 | | | — | — | — | — | — |

높이가 7인 탑이 들어온다. stack에 있는 높이 5인 탑과 비교했을 때 더 높으므로 stack에 있던 (2, 5) 가 pop된다. 그리고 아직 stack 에 남아있는 (1, 9) 와 비교한다. 이 때, 높이 7인 탑이 더 낮으므로 (1, 9) 는 pop 되지 않으며, stack에 (3, 7) 이 추가된다. 수신할 수 있는 탑이 있으므로 result에는 높이 9인 탑의 번호인 2가 들어간다.

다섯번째 탑 : 4

stack

| [1,9] | [3,7] | | | | | — | — | — | — | — |

answer

| 0 | 0 | 2 | 2 | 4 | | — | — | — | — | — |

높이가 4인 탑이 들어온다. stack에 있는 높이 7인 탑과 비교했을 때 더 낮으므로 stack에 있던 탑들은 그대로 남아있고 뒤에 (4, 4)가 추가된다. 수신할 수 있는 탑이 있으므로 result에는 높이 7인 탑의 번호인 4가 들어간다. (높이가 7인 탑의 index가 3인 것이므로 탑의 번호는 index+1해서 4가 된다.)

flow

num은 탑의 수를, tower리스트에는 각 탑의 높이를 입력받는다.
입력받은 tower 리스트에 있는 값들을 stack에도 넣어준다.
for문을 통해서 탑을 반복한다.
1. stack이 없다면, 즉 처음이라면 수신할 탑이 없기 때문에 answer에 0을 append한다.
2. stack이 있다면 stack의 마지막값의 높이(stack[-1][1])를 꺼내서 tower[i]와 비교한다. stack의 값이 더 크다면, answer리스트에 stack에 저장된 인덱스값을 넣어준다. (이때, +1해주어야 한다) 반복문 안에 있기 때문에 break한다. 이를 stack에 값이 있는 동안 반복한다.
3. stack이 있든, 없든, 안에 있는 것이 크든 작든 일단 하나씩 stack에 넣어주기 때문에 stack에 tower의 인덱스와 높이를 함께 집어넣어준다.
answer리스트를 출력한다. 이때 공백을 두고 출력해야 한다.
1. 방법은 3가지가 있다.
  1. for i in range (answer): prin(i, end=’ ‘)
  2. print(' '.join(map(str, result)))
  3. print(*answer)

🚩My submission

  
n = int(input())
tower = list(map(int, input().split()))
stack = []
answer = [0] * n

for i in range(n):
    while stack:
        if stack[-1][1] > top_list[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, result)))

🚩Others submission

다른 코드1

  
import sys

n = int(sys.stdin.readline())
top = list(map(int, sys.stdin.readline().split()))
stack = [] # 비교할 탑의 스택
res = [0] * n

# 반복문을 통해 탑의 높이를 확인
for i in range(n):
    # 스택에 탑이 있는지 확인
    if stack:
        while True:
            # 비교해야하는 탑의 높이와 스택에 마지막 탑의 높이를 비교
            # 스택에 마지막 탑의 높이가 더 클 때
            if top[i] <= stack[-1][0]:

                # 현재 탑의 레이저 신호를 수신해야하는 탑이 스택에 마지막 탑이 된다.
                # 스택에 마지막 탑의 위치를 결과 리스트에 + 1 해주어 초기화
                res[i] = stack[-1][1] + 1
                stack.append([top[i], i]) # 현재 비교한 탑의 높이를 추가하고 반복을 멈춘다.
                break

            # 스택에 마지막 탑의 높이가 작다면 마지막 탑을 팝한다.
            # 현재 탑의 높이보다 작은 스택에 마지막 탑은 수신할 수 없기 때문에 팝
            else:
                stack.pop()

            # 스택에 탑이 없을 경우 스택에 현재 높이의 탑을 추가하고 반복을 멈춘다.
            if not stack:
                stack.append([top[i], i])
                break

    # 스택에 탑이 없으면 현재 비교해야하는 탑의 높이와 순서를 스택에 추가
    else:
        stack.append([top[i], i])

print(*res)

다른코드2

  
if __name__ == "__main__":
    N = int(input())  # 탑의 개수
    top_list = list(map(int, input().split()))  # 탑 리스트
    stack = []
    answer = []

    for i in range(N):
        while stack:
            if stack[-1][1] > top_list[i]:  # 수신 가능한 상황
                answer.append(stack[-1][0] + 1)
                break
            else:
                stack.pop()
        if not stack:  # 스택이 비면 레이저를 수신할 탑이 없다.
            answer.append(0)
        stack.append([i, top_list[i]])  # 인덱스, 값

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

다른코드3

  
import sys
r = sys.stdin.readline

# 입력 받기
n = int(r())
t_list = list(map(int, r().split()))
answer = []
stk = []
for i in range(n):
    h = t_list[i]
    if stk:
        #print(stk)
        while stk:
            if stk[-1][0] < h :
                stk.pop()
                if not stk:
                    print(0, end=' ')
            elif stk[-1][0] > h:
                print(stk[-1][1]+1, end=' ')
                break
            else : 
                print(stk[-1][1]+1, end=' ')
                stk.pop()
                break
        stk.append([h, i])
    else:
        print(0, end=' ')
        stk.append([h,i])

다른코드4

  
import sys
 
input = sys.stdin.readline
n = int(input())
tower_list = list(map(int, input().split()))
stack = []
result = [0] * n
for i in range(n):
    tower = tower_list[i]
    while stack and tower_list[stack[-1]] < tower:
        stack.pop()
    if stack:
        result[i] = stack[-1] + 1
    stack.append(i)
print(' '.join(map(str, result)))

여기서 stack의 의미는 수신이 가능한 탑이다.

10번째 줄의 while문의 의미는 어차피 i번째 타워보다 낮은 타워는 i+1번째 이상의 타워들에서 의미가 없기 때문에 비교에서 제거한다. 즉, 어차피 (i+α)번째 tower가 i번째 tower보다 낮을 경우 최소 i번째 tower에서 수신을 하기 때문에 (i-α)번째 tower는 비교를 위한 stack에 존재할 이유가 없다. 12번째 줄 if stack의 경우, 만약 i번째 tower 왼쪽에 수신 가능한 더 높은 tower가 있다면 반드시 stack안에 존재하므로 stack 마지막 값을 위치로 지정해준다. 마지막에는 해당 타워를 비교 대상에 넣어준다.

💡Retrospect

스택을 활용한 문제였다. 그래서 그동안 했던 것을 또 한번 복습할 수 있었다. 스택과 관련된 문제는 이제 어떤 유형인지 잘 파악되는 것 같다.
이 문제에서는 인덱스를 같이 스택에 저장한다는 아이디어를 떠올리기가 쉽지가 않았다. 또한 앞으로도 스택에 어떤 것을 저장해야 할지 (dp도 마찬가지) 잘 파악해야 할 것 같다.
새로 배운 것 : 출력하는 방법이 여러가지라는 것. 1. for i in range (answer): prin(i, end=’ ‘) 2. print(' '.join(map(str, result))) 3. print(*answer)

백준 - 2493. 탑 (MJ)

#2493. 탑

📖Problems

🔍Institution

🔍Approach

🚩My submission

🚩Others submission

💡Retrospect

Further Reading

백준 - 1956. 운동 (MJ)

백준 - 4949. 균형잡힌 세상 (MJ)

백준 - 10733. 제로 (MJ)