[프로그래머스] 숫자 게임 / 파이썬 / (정렬, 이진 탐색)

https://programmers.co.kr/learn/courses/30/lessons/12987#

풀이

예전에 풀어봤던 문제다.
핵심은 비교값보다 큰 값이 있다면, 큰 값 중 가장 작은 값을 내고
비교값보다 큰 값이 없다면 가장 작은 값을 내는 것이다.

정렬과 이진 탐색을 이용해서 풀었다.
한 번은 직접 구현했고, 한 번은 라이브러리 사용을 했다.

직접 구현

def solution(A, B):
    answer = 0
    B.sort()

    def b_search(val):
        start = 0
        end = len(B)-1
        while start < end:
            mid = (start + end) // 2
            if B[mid] > val:
                end = mid
            else:
                start = mid + 1
        return end

    for a in A:
        idx = b_search(a)
        if B[idx] > a:
            B.pop(idx)
            answer += 1
        else:
            B.pop(0)
    return answer

라이브러리 사용

import bisect
def solution(A, B):
    answer = 0
    B.sort()

    for a in A:
        idx = bisect.bisect_right(B, a)
        if idx == len(B):
            B.pop(0)
        else:
            B.pop(idx)
            answer += 1
    return answer

더 나은 풀이로는?

조금 더 생각해보면, 이진 탐색을 하지 않아도 되는 문제이다.

def solution(A, B):
    answer = 0
    A.sort()
    B.sort()
    j = 0

    for i in range(len(A)):
        if A[j] < B[i]:
            answer = answer + 1
            j = j+1

    return answer