[프로그래머스] Lv3. 숫자 게임

🔗

풀이

각 배열의 최대 길이가 10만이라 혹시 몰라서 힙을 썼는데 그 정도 문제는 아니었던 것 같다. O(n)이내에 통과할 수만 있으면 힙을 쓰지 않아도 가능하다.

순서가 반드시 지켜지지 않아도 상관없으므로 두 배열을 정렬해서 각각의 값을 비교한다. A배열 현재 인덱스 값을 B배열 인덱스 값으로 이길 수 없다면 B배열 인덱스를 1 증가시킨다. 이길 수 있다면 두 값 모두 인덱스를 증가시키고 카운트를 1 증가시킨다.

두 배열 중 하나라도 더 비교할 인덱스가 남아있지 않다면 종료한다.

def solution(A, B):
    heapify(A)
    heapify(B)

    answer = 0
    while True:

        if A[0] >= B[0]:
            heappop(B)
        elif A[0] < B[0]:
            answer += 1
            heappop(A)
            heappop(B)
        if not A or not B:
            break

    return answer

from heapq import heapify, heappop, heappush