[프로그래머스] 숫자 게임 - Python

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

프로그래머스

---

• 풀이1
  • heap
    • 최대힙
    • 가장 큰 사람끼리 비교
      • B팀이 이기면 +1
        • 다음으로 가장 큰 사람끼리 비교
      • 그렇지 않으면 B팀의 가장 큰사람이 다음 경기에 투입
        • 다음으로 가장 큰 A팀 사람과 경기
• 코드1

import heapq

def solution(A, B):
    answer = 0
    # A와 B를 heap으로 만들기(최대힙)
    A = [-i for i in A]
    B = [-i for i in B]
    heapq.heapify(A)
    heapq.heapify(B)
    while B and A:
        # A팀에서 가장 큰 수 
        a = heapq.heappop(A)
        # B팀에서 가장 큰 수 
        b = heapq.heappop(B)
        # B팀 이김
        if -a < -b:
            answer += 1
        # B팀이 이기지 못함
        # 현재 B팀의 가장 큰 수를 다음 A팀의 가장 큰 수 와 경쟁
        else:
            heapq.heappush(B,b)
    return answer

 

•  풀이2
  • 두 팀 다 오름차순으로 정렬
  • A, B 팀 작은 선수끼리 비교
    • B팀은 계속 다음 선수로
    • A팀은 B팀이 이긴경우에만 다음 선수로
• 더 효율적인 코드

def solution(A,B):
	answer = 0
    A.sort()
    B.sort()
    j = 0
    for i in range(len(B)):
    	# B팀이 이겼다면 다음 A팀 나오기
        if A[j] < B[i]:
            answer += 1
            j += 1
    return answer