BOJ3015 오아시스 재결합
골드I | 백준 3015 | Python3 파이썬 풀이
분기가 많아 까다로운 문제이다. 알고리즘의 핵심은 각 키에 대해 분기를 크게 세 개로 나눌 수 있다. 키가 작은 경우, 큰 경우, 같은 경우이다. 이때, 시간복잡도를 낮추기 위해 스택을 이용한다.
특정 인덱스의 키에 대해 그 위치에서부터 앞쪽으로 볼 수 있는 사람들을 카운트한다.
어떤 두 사람이 서로 볼 수 있으려면, 그 두 사람 사이에 그들보다 키가 큰 사람이 없어야 한다. 만약 현재 스택에 top의 키보다 큰 키가 뒤쪽에 있다면 그 이후 사람들은 절대 현재 스택의 top 값을 볼 수 없다. 즉, 현재 스택의 top을 버린다(pop).
만약, 현재 스택에 top의 키보다 작은 키가 있다면 그 값은 후보군에 추가하기 위해 stack에 push한다.
stack에는 키 뿐만 아니라, 해당 키를 볼 수 있는 사람의 수도 함께 넣어주어야 한다.
만약 stack의 top에 있는 사람의 키를 이라고 할 때,
현재 스텝의 키를 라고 하면,
만약 라면, 이후 사람은 를 볼 수 없으므로 를 버리기 전, count
를 증가시키고, 만약 라면 현재 를 볼 수 있는 사람은 도 볼 수 있으므로 현재 를 볼 수 있는 사람 수를 저장하는 nowcount
에 수를 더해준다.
만약 라면, 서로 볼 수 있으므로 count
를 증가한다.
import sys
input = sys.stdin.readline
N = int(input())
heights = [int(input()) for _ in range(N)]
count = 0
stack = []
for height in heights:
nowcount = 1
while stack:
if height >= stack[-1][0]:
count += stack[-1][1]
# 현재 스택의 top과 키가 같다면
if height == stack[-1][0]:
# 볼 수 있는 사람 수를 더해준다
nowcount += stack[-1][1]
# 더 이상 stack의 top을 볼 수 있는 사람이 없으므로
# 스택에서 버린다.
stack.pop()
else:
# 서로 볼 수 있는 쌍
count += 1
break
# 스택에 해당 키를 넣는다
# 이때, 현재 사람을 볼 수 있는 카운트를 추가
stack.append((height, nowcount))
print(count)
어려운 문제인 것 같다. (곧 플래5로 올라갈수도)