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

programmers.co.kr/learn/courses/30/lessons/12987

코딩테스트 연습 - 숫자 게임

 

처음에는 그냥 sort해서 풀면 되는거 아닌가? 하다가 효율성에서 걸리겠지? 하고 걍 내봤는데 답도 틀렸다고해서 ? 싶었다ㅠㅠ 계속 오름차순으로 정렬하려고 한게 삽질의 원인인듯🤔

푸는 방법을 검색해봤더니!

1. min(A) >= max(B) 이면 하나도 이긴게 없다는 말이니까.. 바로 0 리턴
2. A와 B를 내림차순 정렬.
   A[0]와 B[0]를 비교하여 지거나 비기면 continue -> A[1]과 B[0]을 비교... 반복
   이기면 answer += 1 하고 B에서 pop

이렇게 간단할수가ㅠㅠ 다들 천재같다..

 

아 근데 여기서 중요한게 B를 내림차순으로 정렬할 때, 가장 큰 숫자를 빠르게 제거하기 위해 heapq를 사용하고

최대힙을 쓰기위해 부호를 바꾸는 방식을 사용한다! 그래서 A와 B를 비교할 때에도 절대값을 취하거나 -1을 곱해줘야 한다.

 

 

🙋‍♀️ 작성한 코드

import heapq
def solution(A, B):
    answer = 0
    
    if min(A) >= max(B):
        return 0
    
    A.sort(reverse = True) #A를 내림 정렬
    
    B = [-b for b in B]
    # print(B)
    heapq.heapify(B)
    
    for i in range(len(A)):
        if A[i] >= B[0]*-1 : #지거나 비기면
            continue
        else:
            heapq.heappop(B)
            answer += 1
    
    return answer