백준 3015: 오아시스 재결합(python)

문제

---

어렵다...

 

"n명의 사람들 a, b, c, ... n이 서 있을 때 b의 키가 a보다 크다면 a는 b부터 n까지의 모든 사람을 보지 못함"의 아이디어를 떠올리는 게 중요한 듯 하다.

N명의 사람들을 arr 배열에 저장하고, arr의 원소 i에 대해 i 다음의 사람들을 스택에 넣었다 빼면서 볼 수 있는 사람 수를 카운트한다.

for i in arr:
	# i와 stack[-1]에 대해 카운트

 

case 1: 현재 사람이 스택 최상단의 사람보다 키가 클 경우

while stack and i > stack[-1][0]	# stack에는 (키, 개수) 형태로 저장
	res += stack.pop()[1]	# 다음 사람을 제거하고(조합에 포함되었으므로) 그 카운트를 결과에 추가

현재 사람(i)이 스택 최상단 사람(stack[-1], 가장 최근에 만난 사람)보다 키가 크다면 stack[-1] 사람은 i 다음 사람들을 볼 수 없으므로 제거하고(pop) res에 포함

-> stack에 남아 있는 값을 모두 제거하기 위해 while문 사용, i보다 작은 사람들을 모두 배제

 

case 2: 현재 사람과 스택 최상단 사람의 키가 같을 경우

- case 2-1: i와 stack[-1]이 서로 볼 수 있으므로 pop하고 res에 포함

- case 2-2: 스택에 stack[-1]보다 큰 사람이 있는 경우 - 해당 사람과도 서로 볼 수 있으므로 res + 1

if i == stack[-1][0]:   # 같을 때
	cnt = stack.pop()[1]
	res += cnt

	if stack:	# 작은 값은 이미 모두 pop되었을 것이므로 값이 남아 있다면 더 큰 값 
		res += 1
	stack.append((i, cnt + 1))

 

case 3: 현재 사람이 스택 최상단 사람보다 작을 경우:

else:
	stack.append((i, 1))
    res += 1

i와 stack[-1]은 볼 수 있으므로 res + 1, 그 다음에 등장하는 사람들과 비교해야 하므로 스택에 append

 

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = [0 for _ in range(N)]
for i in range(N):
    arr[i] = int(input())

stack = []  # (height, count)
res = 0

for i in arr:
    while stack and i > stack[-1][0]:    
        res += stack.pop()[1]

    if not stack:  
        stack.append((i, 1))
        continue

    if i == stack[-1][0]:
        cnt = stack.pop()[1]
        res += cnt

        if stack:
            res += 1
        stack.append((i, cnt + 1))
    else:
        stack.append((i, 1))
        res += 1

print(res)