[Python/스택] 2.뒤통수가 따가워

출처: 구름 알고리즘 먼데이 챌린지 8주차

문제

구름나라의 저편에 있는 무릉도원에는 높은 산봉우리들이 있는 산맥이 있다. 모든 산봉우리에는 동쪽을 바라보며 명상을 하는 신선이 한 명씩 있다. 그러던 중 신선들은 다른 신선들이 자신의 뒤통수를 바라봐서 그런지 뒤통수가 따가워짐을 느끼다가, 문득 얼마나 많은 신선이 자신의 뒤통수를 볼 수 있는지 궁금해졌다. 

산맥의 모든 봉우리들은 왼쪽에서 오른쪽으로 정확히 일렬로 놓여있다. 왼쪽에서 a번째 봉우리에 있는 신선이  b번째 봉우리에 있는 신선의 뒤통수를 보기 위해선, a<b 이면서 두 봉우리 사이에 있는 모든 봉우리의 높이가  a번째 봉우리의 높이보다 작아야 한다. 중간에 높은 봉우리가 있으면 그 뒤쪽 봉우리는 가려져서 보이지 않기 때문이다.

신선들의 궁금증을 해결해주기 위해, 산맥에 있는 봉우리의 개수와 각 봉우리의 높이를 알려주면 각 신선마다 그 신선의 뒤통수를 볼 수 있는 신선의 수를 출력하는 프로그램을 만들어보자.

---

입력

첫 번째 줄에는 봉우리의 수를 나타내는 정수 N(5<=N<=100,000) 이 주어진다.
두 번째 줄에는 봉우리의 높이가 왼쪽에서부터 순서대로 주어진다. 

각 봉우리의 높이는  10^9이하의 양의 정수이다.

 

출력

어떤 신선의 뒤통수를 볼 수 있는 신선의 수를, 가장 서쪽의 봉우리에 있는 신선부터 순서대로 공백으로 구분하여 출력한다.

 

예제 입력	예제 출력
5 4 3 2 4 1	0 1 2 3 1
10 19 11 4 10 19 11 4 7 6 18	0 1 2 3 3 1 2 3 3 4

---

풀이

[문제 요약]

각 봉우리에 대해서 '몇 개의 봉우리에서 해당 봉우리가 보이는 가'를 구하자
a가 b를 보기 위해서는 a<b이고 
a와 b 사이 봉우리는 a의 높이보다 작아야 한다. (a봉우리가 b봉우리보다 높을 필요는 없다)

# *** 오답: 테케 Timeout ***
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

answer = ['0'] # join을 하려면 str이여야 함 (0 안됨!)

for b in range(1, len(arr)): 
	cnt = 1
	for a in range(0, b-1):
		if max(arr[a+1:b]) < arr[a]:
			cnt += 1
	answer.append(str(cnt))

#print(answer)
temp = " ".join(answer)
print(temp)

Last-In-First-Out 구조의 스택을 사용하면 된다.

a,b번 봉우리 사이에 a보다 높은 봉우리가 있으면 안된다는 조건을 스택을 사용해 쉽게 처리할 수 있다.

i번째 봉우리의 높이 값까지 연산을 진행한 스택에는, i+1번째 봉우리를 볼 수 있는 봉우리들의 높이값만 저장되어 있다. 

즉, 스택에 저장된 값의 개수가 i+1번째 봉우리를 보는 봉우리의 수이다.

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

stack = [] # 봉우리를 볼 수 있는 신선을 담는다 (len(stack)은 봉우리를 볼 수 있는 신선의 수)

for i in range(N):
	print(len(stack), end=' ') # i번째일 때 i+1번째 봉우리를 볼 수 있는 신선을 담음
	while stack and stack[-1] <= arr[i]: # stack 마지막부터 arr[i]보다 큰 값은 제거 함
			stack.pop()
	stack.append(arr[i]) # idx가 증가함에 따라 고려해야하는 신선이 하나 더 추가됨

i = 3일 때 (마지막 봉우리를 볼 수 있는 봉우리 계산할 때)   

stack의 모든 값([4,3,2]은 arr[i]인 4보다 작기 때문에 while문에서 모든 원소를 pop을 해서 []가 된다.

그리고 stack에 arr[i]를 append해준다.

append를 pop 이후에 해주는 이유는 첫번째 봉우리가 아닌 모든 봉우리는 최소 한 명의 신선(직전 봉우리)이 볼 수 있기 때문이다.

 

idea: i일때 i+1의 봉우리 수를 계산해서 print를 먼저 해주기

 

 

📝

한줄로 출력

print(item, end=' ')