[Python/파이썬] Summer/Winter Coding(~2018) 숫자 게임

프로그래머스

코드

• 효율성 0점 코드

from collections import deque

def solution(A, B):
    answer = 0
    B = deque(sorted(B))
    for idx in range(len(A)):
        tmp = deque([])
        now = B.popleft()
        while True:
            if now > A[idx]:
                B = tmp + B
                answer += 1
                break
            else:
                tmp.append(now)
                if not B:
                    tmp.popleft()
                    B = tmp + B
                    break
                else:
                    now = B.popleft()
    return answer

정확성 테스트는 통과했지만 효율성이 모두 시간 초과로 0점 나왔다. 

코드를 간단히 설명해보자면 A 배열의 값들에 대해 매번 B에서 이길 수 있는 가장 작은 값을 사용하도록 했다...

1. B를 정렬시키고 deque로 만들어서 A의 이번 인덱스의 값을 이길 수 있는 값이 나올 때까지 B배열의 앞에서부터 뽑아낸다.
2. 이길 수 있는 값이 나오면 뽑아냈던 값들을 다시 B배열에 합쳐준다. 배열은 어차피 이미 정렬된 배열을 순서대로 뽑아서 tmp 배열에 넣었으니 정렬은 다시 신경쓰지 않아도 된다.

효율성이라고는 찾아볼 수가 없는 코드이긴 했다. 그래서 다시 머리를 굴려서 이분탐색으로 도전...

def bin_search(x, arr, used):
    start, end = 0, len(arr) - 1 
    find_idx = -1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == x:   # 동점 => 점수 못 얻음 => 이전에 저장된 arr[find_idx]가 이길 수 있는 최소값
            break
        elif arr[mid] > x:
            find_idx = mid
            end = mid - 1
        else:
            start = mid + 1            
            
    while used[find_idx]:
        find_idx += 1
        if find_idx == len(arr):    # 이 위로는 이미 다 쓴 것들이어서 쓸 수 없음 => 제일 작은 놈 소모하고 이번 판은 진다
            find_idx = 0
    used[find_idx] = True
    return arr[find_idx]

def solution(A, B):
    answer = 0
    B = sorted(B)
    used = [False for _ in range(len(B))]
    
    for el in A:
        now = bin_search(el, B, used)
        if now > el:
            answer += 1
    return answer

 

이분탐색을 하는데 이미 쓴 숫자들은 다시 사용할 수 없으니 used 배열에 표시해가며 진행하도록 하였다.

이렇게 하니 

또 실패했다....도저히 모르겠어서 질문에 누가 힌트를 남긴 걸 봤더니 A 배열을 고정시키고 해야한다는게 큰 착각이라는 힌트를 보고 다시 생각해봤더니 쉽게 풀 수 있었다.

import heapq

def solution(A, B):
    answer = 0
    
    heapq.heapify(A)    
    heapq.heapify(B)    
    
    a = heapq.heappop(A)
    b = heapq.heappop(B)
    
    while True:
        if a >= b:  # B팀이 이길 수 없다면 이번에 나온 숫자는 버림
            if B:
                b = heapq.heappop(B)
            else:
                break
        else:
            answer += 1
            if not A:
                answer += len(B)
            if not B:
                break
            a = heapq.heappop(A)
            b = heapq.heappop(B)
                
    return answer

생각해보니 A팀의 순서도 고정해놓고 생각할 필요 없었다. B가 최대 몇 번 이길 수 있는지를 구하면 되는 문제이므로 A, B를 오름차순 정렬해놓고 하나씩 pop해가며 비교하면 되는 문제였다. heapq를 이용하여 최소힙을 만들고 heappop해가며 비교하였다. 매번 pop된 원소들은 남은 원소들 중 가장 작은 원소이므로 현재 pop된 B의 원소가 현재 pop된 A의 원소를 이기지 못한다면 B의 원소는 쓸모없는 것이니 그건 버리고 B를 다시 pop하여 비교하면 된다. 

이렇게 풀이하니 효율성 테스트도 훨씬 빠르다...