[Baekjoon 3020] 개똥벌레

문제

💛Ⅴ [Baekjoon 3020-개똥벌레]

문제 풀이 방법

이진 탐색을 사용하여 풀이해야 하는 문제이지만, 어느 부분에서 이진 탐색을 사용해야 하는지를 파악하기가 힘들었다. 그래서 그냥 각 장애물의 길이에 따라 높이 별 count 변수에 값을 저장하는 방식으로 풀었더니 시간초과가 떴다. 질문 게시판을 참고하여 이분탐색을 어디에서 찾아야 하는지 참고하여 다시 풀어보았다!

1) 처음에 장애물을 석순(길이)과 종유석(H-길이)을 나누어 입력을 받고, 각각 정렬을 한다.

2) H만큼 반복문을 돌면서 각 장애물 배열( down_obstacle, up_obstacle )에서 h보다 큰 장애물이 있는 index를 찾는다. 이 때 이분탐색은 Python의 bisect 라이브러리를 활용하였다.

3) 장애물의 개수는 down_obstacle의 경우 (배열의 길이-index)이고, up_abstacle의 경우는 찾은 index이다.

4) 각 높이마다 센 장애물의 개수 배열에서 최솟값과 그 개수를 print한다.

풀이 코드

Python - 시간초과

import sys
input = sys.stdin.readline

N, H = map(int, input().split())
obstacle = [int(input()) for _ in range(N)]

cnt = [0] * H
for i,x in enumerate(obstacle):
    if i%2==0:
        for idx in range(H-1,H-x-1,-1):
            cnt[idx]+=1
    else:
        for idx in range(0,x):
            cnt[idx] += 1

min_cnt = cnt[0]
answer = 0
for c in cnt:
    if min_cnt > c:
        min_cnt = c
        answer = 1
    elif min_cnt == c:
        answer += 1
print(min_cnt, answer)

Python - 통과!

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

N, H = map(int, input().split())
down_obstacle = []
up_obstacle = []
for i in range(N):
    if i%2 == 0:
        down_obstacle.append(int(input()))
    else:
        up_obstacle.append(H - int(input()))
down_obstacle.sort()
up_obstacle.sort()

cnt = [0] * (H+1)
for i in range(1,H+1):
    cnt[i] = (N//2 - bisect_left(down_obstacle,i)+bisect_left(up_obstacle,i))

min_cnt = cnt[1]
answer = 0
for c in cnt[1:]:
    if min_cnt > c:
        min_cnt = c
        answer = 1
    elif min_cnt == c:
        answer += 1
print(min_cnt, answer)