[알고리즘] 카드 게임(Easy & Hard)

레벨 인터뷰 하면서 받았던 피드백을 반영해보자 세웠던 액션 플랜을 준비하기 위한 글이다. 

 

 

 

나는코더다에서 카드 게임(Easy)와 카드 게임(Hard)라는 문제가 나왔다. 

 

Easy

문제 요약

Easy는 상대의 체력 $H$와 내가 가지고 있는 공격력 카드 $N$장과 그리고 각 공격력 카드의 공격력 $d_i$이 주어진다. 카드를 사용하면 상대의 체력은 $d_i$ 만큼 깎이고, $H$가 0이하가 되면 게임은 끝난다. 그리고 각 카드는 한번씩만 사용할 수 있다. 최대한 많은 카드를 사용고자할 때 최대 몇 개의 카드를 사용할 수 있는지를 구하는 문제이다. 모든 카드를 사용하여도 $H$를 만들지 못하면 -1을 반환한다.

 

문제 접근

정리하면 최대한 많은 카드를 사용하여 $H$ 이상을 만들어야 한다. $H$ 이상을 만들 때 최대한 많은 카드를 사용하려면 더하는 카드들의 공격력이 낮아야 한다. 즉 낮은 공격력 카드를 우선적으로 더하며 $H$ 이상이 되는지 확인하면 되는 문제이다. 

 

코드

 

 

import sys
input = sys.stdin.readline
 
n,h = map(int,input().split())
nums = list(map(int,input().split()))
 
cur = 0
for i in range(n):
    cur += nums[i]
    if cur >= h:
        print(i + 1)
        break
else:
    print(-1)

 

Hard

문제 요약

Easy와 동일하게 공격력 카드를 사용해서 상대의 체력을 0이하로 만드는 것이 목적이다. 최대한 적은 카드를 사용하여 게임을 끝내는 것이 Easy와 다른 점이고, 또 Hard에서 추가된 것은 $Q$ 개의 카드가 차례대로 추가된다. 

 

문제 접근

$Q$개의 카드가 추가될 때마다 이전에 있던 카드덱에 삽입하고 재정렬하여 계산을 한다면 $QNlogN$이고 $Q$와 $N$의 최대값은 $300,000$임으로 제한 시간 1초 안에 수행이 불가능하다. 하지만 원소 추가시 정렬을 효율적으로 해주는 힙을 사용한다면 $O(QlogN)$으로 줄일 수가 있다. 

 

힙을 사용시 정렬된 상태를 유지한 채 원소삽입이 가능한 이유는 힙은 완전이진트리 형태를 갖추기 때문이다. heappop() 메서드를 사용하면 $O(1)$ 만에 최소값을 가져올 수 있다. 인덱스 접근 역시 가능한데, 제일 첫번째 요소 hq[0]을 제외하고는 순서대로 정렬되어 있지 않을 수 있다. 즉 hq[3]의 값이 hq에서 네번째로 큰 값이 아닐거라는 이야기이다. 정렬된 상태로 원소를 확인하고 싶다면 heappop() 메서드를 사용하여 확인해야 한다. 왜냐하면 힙은 heappop() 메서드를 호출하여 원소를 삭제할 때마다 이진 트리의 재배치를 통해 매번 새로운 최소값을 0번째 인덱스로 위치시키기 때문이다. 

 

삽입을 하는 heappush()와 제거를 하는 heappop() 외에도 위 문제를 풀기 위해 heapify()와 heapreplace() 메서드를 사용하였다. heapify() 메서드는 리스트를 힙 자료구조로 변경해주는 메서드이고 시간 복잡도는 $O(n)$이다. heapreplace()는 heappop() 후 heappush() 메서드를 사용한 것과 동일한 결과를 반환하는데, 이 두 메서드를 결합하여 사용하는 것보다 heapreplace() 메서드를 사용하는것이 더 효율적이다. 이유는 heappop()과 heappush() 메서드를 사용한다면 연산이 두번 발생하고 이로인한 오버헤드와 두 번의 힙 조정이 발생하지만 heapreplace()는 한 번의 힙 조정만 발생한다. 이론적으로 heapreplace()를 사용한다면 $O(logN + logN)$ 을 $O(logN)$으로 줄일 수 있다. 

 

힙에 있는 원소의 합이 H 이상이되 힙 사이즈를 최소로 유지하도록 하였다. 

 

코드

 

from heapq import heappop, heappush, heapify, heapreplace
import sys
input = sys.stdin.readline
 
h = int(input())
n,q = map(int,input().split())
nums = list(map(int,input().split()))
nums.sort(reverse=True)
 
cur = 0
hq = []
for i in range(n):
    cur += nums[i]
    hq.append(nums[i])
    if cur >= h:
        print(i + 1)
        break
else:
    print(-1)
 
heapify(hq)
 
for _ in range(q):
    x = int(input())
    if cur < h: 
        heappush(hq, x)
        cur += x
        if cur < h:
            print(-1)
            continue
        tmp = cur
        ans = len(hq)
        while hq and tmp - hq[0] >= h:
            tmp -= heappop(hq)
            ans -= 1
        cur = tmp
        print(ans)
    elif hq and hq[0] < x:
        tmp = cur - hq[0] + x
        heapreplace(hq, x)
        ans = len(hq)
        while hq and tmp - hq[0] >= h:
            tmp -= heappop(hq)
            ans -= 1
        cur = tmp
        print(ans)
    else:
        print(len(hq))