[백준] 3020번: 개똥벌레 (bisect 활용하기)

https://www.acmicpc.net/problem/3020

---

import sys
import math
from collections import Counter
from bisect import bisect_left

sys.stdin = open("input.txt")

n, h = map(int, sys.stdin.readline().split())

bottom = []
top = []

for i in range(n):
    tmp = int(sys.stdin.readline().rstrip())
    if i % 2 == 0:
        bottom.append(tmp)
    else:
        top.append(tmp)

bottom.sort()
top.sort()

min_num = float("inf")
min_cnt = 0

for i in range(1, h+1):
    bottom_idx = bisect_left(bottom, i)
    top_idx = bisect_left(top, (h+1)-i)

    num = n - (bottom_idx + top_idx)

    if num < min_num:
        min_num = num
        min_cnt = 0

    if num == min_num:
        min_cnt += 1

print(min_num, min_cnt)

 

알고리즘 분류:

- 이진 탐색

- 누적 합

 

Key Points:

시간초과로 애먹었던 문제... 처음에는 binarySearch() 함수를 만들어서 모든 height에 대해 탐색하면서 막 이러쿵 저러쿵 해봤는데 지금 생각해보니 조금 비약이 있는 로직이었던 것 같고, 가장 큰 문제는 애초에 시간 제한을 통과하지 못했다. 그래서 로직 자체를 처음부터 다시 생각해보았다. 만약 석순이 높이를 기준으로 오름차순 정렬되어있다면 개똥벌레가 높이 3으로 지나간다고 했을 때 처음으로 높이 3의 석순이 나타나는 이후의 석순들은 모두 파괴할 수 밖에 없다(모두 높이가 3 이상일 것이기 때문에). 이를 코드로 구현하기 위해 bottom(석순), top(종유석) 리스트를 우선 정렬해준 뒤, 각각 높이 i 이하의 값이 처음으로 나타나는 인덱스를 기준으로 이후에 나타나는 모든 값들을 cnt에 더해주었다. 이 때. 석순은 바닥을 기준으로 높이가 시작되기 때문에 크게 신경 쓸 것이 없지만, 종유석의 경우 천장을 기준으로 높이를 계산하기 때문에 (h+1)-i 와 같이 반대로 뒤집어서 생각을 해줘야 한다. 가장 중요한 것은 어떻게 하면 높이 i가 처음으로 나타나는 인덱스를 찾을 것인가 인데 for문으로 선형 탐색 하자니 시간이 너무 오래 걸릴 것 같고, 처음에는 binarySearch() 함수를 만들어서 활용할까 하다가 마침 파이썬 내장 라이브러리 중 bisect라고 하는 좋은 라이브러리가 있다는 것이 생각나서 이를 활용했다. bisect_left는 target값이 가장 처음으로 나타나는 인덱스를 return하고 bisect_right는 target값 있는 인덱스 중 가장 마지막 인덱스를 return한다. 앞으로도 이진 탐색으로 문제를 접근할 때 가장 먼저 bisect 라이브러리를 활용할 수 있는 방법이 있을 지 먼저 생각해봐야겠다. 좋은 라이브러리는 활용해야지.

 

기억할 만한 문법:

bisect_left(list, target): list 중 target값이 나타나는 가장 첫번째 인덱스를 return

bisect_right(list, target): list 중 target값이 나타나는 가장 마지막 인덱스를 return