[Baekjoon Online Judge] 백준 11003번 탑(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11003번 탑

(Python)

(글쓴날 : 2020.05.13)

 

---

* Baekjoon Online Judge, 백준 11003번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 11003번 탑

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2493

2493번: 탑

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

높이가 각기 다른 N개의 탑들이 주어지고 오른쪽 탑부터 왼쪽으로 레이저를 발사할 때, 레이저 수신이 가능한 자신보다 높은 탑의 번호를 구하는 문제입니다.

단, 자신보다 높은 탑이 없을 경우 0을 출력합니다.

 

저의 경우, 스택을 이용했으며, Python을 사용했습니다.

N의 최댓값이 500,000이므로 완전 탐색으로 풀 시 시간 초과가 나게 됩니다.

이에 따라 정렬, 이분 탐색 등 여러 방면으로 풀어보려고 노력했으나 결국 찾지 못했고, 질문 검색을 찾아본 결과 스택으로 푼다는 것을 확인했습니다.

탑들을 차례대로 탐색하여 스택이 비었을 경우 탑의 번호와 높이를 튜플 형태로 스택에 저장하고 스택에 탑이 있을 경우 탐색 중인 탑과 비교하여 만약 크다면 스택 안에 있는 탑의 번호를 출력 후 현재 탑을 스택에 저장하고, 만약 작다면 스택에서 탑들을 계속 꺼내어 비교하는 식으로 문제를 해결했습니다.

왼쪽에서 오른쪽으로 탐색하며 탐색된 탑보다 왼쪽에 작은 탑이 있을 시 탐색 대상에서 제외된다는 원리는 알았지만 어떻게 구현해야 할지를 몰랐는데, 스택을 사용하여 구현할 수 있다는 것을 떠올리지 못한 것이 아쉬웠던 문제였습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
N = int(input())
tower = list(map(int, input().split()))
stack = []
 
for i in range(N):
    while(True):
        if not len(stack):
            print(0, end=" ")
            stack.append((i + 1, tower[i]))
            break
        if stack[-1][1] > tower[i]:
            print(stack[-1][0], end=" ")
            stack.append((i + 1, tower[i]))
            break
        stack.pop()

---