[이분탐색] 백준 3문제 풀이

1. 숫자 카드2

순차 탐색으로 풀 수 있는 방법이지만 시간제한이 있어 이분탐색으로 풀어야 하는 문제다.

틀린 코드

import sys
input = sys.stdin.readline

def count_card(mid,target):
    count=1
    if cards[mid-1]==target: #mid 인덱스 전에 값이 있는지 확인
        for i in range(mid-1,-1,-1):
            if cards[i]!=target:
                break
            count+=1
    if cards[mid+1]==target:#mid 인덱스 후에 값이 있는지 확인
        for i in range(mid+1,n):
            if cards[i]!=target:
                break
            count+=1
    return count

def binary_search(start,end,target):
    while start<=end:
        mid = (start+end)//2
        if cards[mid]==target:
            if mid==0 or mid==n-1:
                return 1
            else:
                return count_card(mid,target)
        elif cards[mid]>target:
            end = mid-1
        else:
            start = mid+1
    
    return 0
    

n = int(input())

cards = list(map(int, input().split()))

m = int(input())

sg = list(map(int,input().split()))

cards.sort() #오름차순으로 정렬


for s in sg:
    print(binary_search(0,n-1,s),end=' ')

이분 탐색을 썼지만 개수를 구하는 단계에서 순차적으로 탐색해서 개수를 더하는 방법을 썼다. => 시간초과 발생

O(nlog n)의 상태에서 또 O(n)의 함수를 중첩해서 시간초과가 발생하였다.

코드1

아이디어

target값을 가지는 최대 인덱스와 최소 인덱스를 구하여
그 둘을 빼면 개수를 얻을 수 있다.

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


n = int(input())

cards = list(map(int, input().split()))

m = int(input())

sg = list(map(int,input().split()))

cards.sort()

for s in sg:
    print(bisect_right(cards,s)-bisect_left(cards,s),end=' ')

python에서 제공하는 upper_bound,lower_bound 역할의 함수를 사용했다.

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

def lower_bound(target):
    start = 0
    end = n-1
    while start<=end:
        mid=(start+end)//2
        if target>cards[mid]:
            start = mid+1
        else:
            end = mid-1
    return start

def upper_bound(target):
    start = 0
    end = n-1
    while start<=end:
        mid =(start+end)//2
        if target>=cards[mid]:
            start = mid+1
        else:
            end = mid-1
    return start
n = int(input())

cards = list(map(int, input().split()))

m = int(input())

sg = list(map(int,input().split()))

cards.sort()

for s in sg:
    print(upper_bound(s)-lower_bound(s),end=' ')

함수를 각각 구현해보았다.

코드2

아이디어2

다른 풀이를 통해 알게 된 아이디어.
딕셔너리를 사용하여 key에는 카드의 숫자, value에는 카드의 개수를 미리 저장하고 sg 리스트에 있는 값을 하나씩 탐색하는 아이디어.

시간복잡도도 O(n)인 코드로 시간 제한이 걸리지 않는다.

import sys
input = sys.stdin.readline

n = int(input())

cards = list(map(int, input().split()))

cards.sort()

count={}

for c in cards: #미리 카드의 개수를 센다
    if c in count:
        count[c]+=1
    else:
        count[c]=1
        
m = int(input())

sg = list(map(int,input().split()))

for s in sg: #count 딕셔너리에 값이 있는지 확인
    if s in count:
        print(count[s],end=' ')
    else:
        print(0, end=' ')

2. 랜선 자르기

아이디어

떡볶이 떡 만들기와 똑같은 문제였다.
다른 점은 개수를 셀 때 나눈 몫을 더해주면 됐다.

코드

import sys
#input = sys.stdin.readline

def cutting(mid):
    count=0
    for a in arr:
        count+= a//mid
    return count

def binary_search(start,end,target):
    result=0
    while start<=end:
        mid =(start+end)//2
        count = cutting(mid)
        if count<target:
            end = mid-1
        else: #적어도 k개 이상이라 했으므로 미리 result에 저장해준다.
            result = mid
            start = mid+1
    return result
            

n,k = map(int,input().split())

arr = []
for i in range(n):
    tmp = int(input())
    arr.append(tmp)
    
end= max(arr)
print(binary_search(1,end,k))

3. 나무 자르기

아이디어

떡볶이 떡 문제랑 똑같았다... 풀었다고 하기 민망...

코드

def remain(h):
    sum=0
    for a in arr:
        if a>h:
            sum+=a-h
    return sum


def binary_search(start,end):
    result=0
    while start<=end:
        h = (start+end)//2
        sum = remain(h)
        if sum<m:
            end = h-1
        else:
            result = h
            start = h+1
    return result

n,m = map(int,input().split())

arr = list(map(int,input().split()))

arr.sort()
start = 1
end = arr[-1]

print(binary_search(start,end))

+) 나무 자르기, 랜선 자르기 둘 다 start의 값을 0으로 두면 zero division error가 발생하기 때문에 start를 1로 두어야 했다.