[백준_2805] 하, 이분 탐색, 수 찾기

[백준_2805] 하, 이분 탐색, 수 찾기

 

 

 

이분 탐색(Binary Search)

 

절단기의 높이를 차례대로 높이는 알고리즘으로는 시간 초과가 발생한다.

이 때 사용할 수 있는게 Binary Search(이분 탐색 or 이진 탐색)을 이용해야 한다.

이진 탐색이란 찾고자 하는 target 값을 오름 차순으로 정렬된 list에서, target값과 list의 중간값 비교를 통해 진행된다.

만약 중간값보다 target이 크면 검색 범위를 중간값 이상의 범위에서 다시 찾기 시작한다. 이 때 중간값은 하기와 같은 새로운 중간값을 이용한다.

 

첫 번 째 코드

import sys
input = sys.stdin.readline

from typing import Any, Sequence

def bin_search(wood: Sequence, pl, pr, need) -> int:
# wood:나무 높이 list, pl : list의 가장 왼쪽, pr : list의 가장 오른쪽, need : 필요한 나무 양
    
    while True:
        cnt =0 # 총 얻어지는 나무 양
        pc = (pl + pr) //2
        for i in range(len(wood)):
            if wood[i] - pc > 0:
                cnt += wood[i] - pc
        if cnt == need : # 얻은 나무 양과 필요한 나무 양이 같을 떄 
            print(pc)
            return
        elif cnt < need : # 얻은 나무 양보다 필요한 나무 양이 많을 때
            pr = pc - 1
        else: # 얻은 나무 양보다 필요한 나무 양이 적을 떄
            pl = pc + 1
        if pl > pr: 
            if cnt < need:
                print(pc-1)
            else:
                print(pc)
            break
    return

x = [int(x) for x in input().split()]
need = x[1]
woods = [int(x) for x in input().split()]

bin_search(woods, 0, max(woods), need)

 

일단 이 방식으로 코드를 구현했을 때, 틀린 이유가 pl, pr 간격이 좁아지다가 같아졌을 때 cnt ==need 조건이 만족되지 않는 조건이 존재 했기 때문이다. 그래서 if pl > pr: ~ 부분을 적었다. 하지만 시간 초과..

 

시간 초과를 해결하기 위해선 2 가지 방법이 있다.

 

 

수정 코드 2 - 효율적인 list를 이용한 방법

import sys
from typing import Any, Sequence

def bin_search(wood: Sequence, pl, pr, need) -> int:
# wood : 나무 높이 리스트, pl : list의 가장 왼쪽, pr : list의 가장 오른쪽, need가 필요 나무 량
    result = 0
    while pl <= pr :
        cnt = 0 # 절단 후 얻은 나무의 양
        pc = (pl + pr) //2

        cnt =[tree - pc if tree > pc else 0 for tree in wood]
        s = sum(cnt) # 절단 후 얻은 나무 양 합

        if s < need :
            pr = pc - 1
        else:
            result = pc
            pl = pc + 1
    return result

x = [int(x) for x in sys.stdin.readline().split()]
woods = [int(x) for x in sys.stdin.readline().split()]
print(bin_search(woods, 0, max(woods), x[1]))

 

가장 중요한 부분은 하기와 같다. 절단 후 얻은 나무의 양을 list를 통해서 바로 얻는 방법인데 if else를 한 문장에서 사용한다.

이걸로 실제로 시간 단축이 꽤 되어 통과되었다.

cnt =[tree - pc if tree > pc else 0 for tree in wood]

 

또한 if문을 줄일 수 있도록 조건의 변화를 주었다. pl <= pr의 조건을 처음부터 걸어주는 것이 조건 충족에 큰 도움이 되었다. 그리고 

cnt == need 일 때만 출력이 되었는데, 이게 안되는 부분을 해결하기 result라는 변수를 추가 하였다. s >= need 일 때 중간값인 pc값을 바로 출력하는 것이 아니라 다시 while 조건문으로 돌아와 pl <= pr 조건문에서 걸러졌을 때 result 값을 return하는 방식이다.

진짜 이런 방식을 어떻게 생각하는 걸까... 이분 탐색을 좀 더  간결하게 쓰는 연습을 해야겠다.

 

 

수정 코드 2 -  Counter 이용

import sys
from collections import Counter
from typing import Any, Sequence

def bin_search(wood: Sequence, pl, pr, need) -> int:
# wood : 나무 높이 리스트, pl : list의 가장 왼쪽, pr : list의 가장 오른쪽, need가 필요 나무 량    
    result = 0

    while pl <= pr :
        cnt = 0
        pc = (pl + pr) //2

        for i, num in wood.items():
            if i > pc:
                cnt += (i - pc) * num
        if cnt < need :
            pr = pc - 1
        else:
            result = pc
            pl = pc + 1
    return result

x = [int(x) for x in sys.stdin.readline().split()]
woods = Counter([int(x) for x in sys.stdin.readline().split()])
print(bin_search(woods, 0, max(woods), x[1]))

 

Collection 모듈의 Counter 클래스를 사용한 방법이다. Counter 클래스를 이용하면 list 안의 원소 값 중 겹치는 개수를 key, value 형식처럼 저장하여 데이터 저장의 효율을 높이는 방식이다. 그래서 굉장한 시간 단축이 가능하다. 하지만 적용을 위해선 위와 같이 사용할 수 있도록 익숙해질 필요가 있겠다.

위와 같이 입력받은 원소들로 구성된 리스트에서 원소 값 별 개수를 저장한다.