BOJ3015 오아시스 재결합

Hoeun Lee·2021년 9월 10일
0

백준 알고리즘 풀이

목록 보기
28/34
post-thumbnail

문제

BOJ3015 오아시스 재결합
골드I | 백준 3015 | Python3 파이썬 풀이


알고리즘

분기가 많아 까다로운 문제이다. 알고리즘의 핵심은 각 키에 대해 분기를 크게 세 개로 나눌 수 있다. 키가 작은 경우, 큰 경우, 같은 경우이다. 이때, 시간복잡도를 낮추기 위해 스택을 이용한다.

특정 인덱스의 키에 대해 그 위치에서부터 앞쪽으로 볼 수 있는 사람들을 카운트한다.

어떤 두 사람이 서로 볼 수 있으려면, 그 두 사람 사이에 그들보다 키가 큰 사람이 없어야 한다. 만약 현재 스택에 top의 키보다 큰 키가 뒤쪽에 있다면 그 이후 사람들은 절대 현재 스택의 top 값을 볼 수 없다. 즉, 현재 스택의 top을 버린다(pop).

만약, 현재 스택에 top의 키보다 작은 키가 있다면 그 값은 후보군에 추가하기 위해 stack에 push한다.

stack에는 키 뿐만 아니라, 해당 키를 볼 수 있는 사람의 수도 함께 넣어주어야 한다.

만약 stack의 top에 있는 사람의 키를 hth_t이라고 할 때,

현재 스텝의 키를 hch_c라고 하면,

만약 ht>hch_t > h_c라면, hch_c 이후 사람은 hth_t를 볼 수 없으므로 hth_t를 버리기 전, count를 증가시키고, 만약 ht=hch_t = h_c라면 현재 hth_t를 볼 수 있는 사람은 hch_c도 볼 수 있으므로 현재 hch_c를 볼 수 있는 사람 수를 저장하는 nowcount에 수를 더해준다.

만약 ht<hch_t < h_c라면, 서로 볼 수 있으므로 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로 올라갈수도)

profile
건국대학교 컴퓨터공학부 이호은 | 알고리즘 정리 블로그

0개의 댓글