PG)숫자 게임 -lv3

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

프로그래머스

 

 

lv3 치고는 매우 쉬운 난이도였다.

 

우선 이 문제는 효율성 테스트가 있기 때문에 처음 제출한 코드는 효율성과 케이스 17번에서 실패했다.

from bisect import bisect_left

def solution(A, B):
    answer = 0
    B.sort()
    A.sort(reverse=True)
    for i in A:
        # print('--------')
        idx = bisect_left(B, i)
        # print('idx = ', idx)
        # print('B = ', B)
        if idx > len(B) - 1:
            continue
        if i < B[idx]:
            answer += 1
            B.pop(idx)
    # print(answer)
    return answer

 

bisect_left로 A의 각 수를 B배열에 알맞은 인덱스를 찾아 해당 B[index]와 A의 원소를 비교해 더 크다면 answer를 +1 해준다.

하지만 A = [1,2,3] B = [1,2,3]과 같은 두 배열의 원소가 일치할 때 두 원소를 알맞게 비교하지 못한다.

 

그래서 효율성을 고려해 힙을 이용해 다시 작성했다.

import heapq

def solution(A, B):
    answer = 0
    A.sort(reverse=True)
    arr = []
    for i in B:
        heapq.heappush(arr,-i)
    
    for a in A:
        num = heapq.heappop(arr)
        if -num > a:
            answer += 1
        else:
            heapq.heappush(arr,num)
        
    return answer