[그리디] Greedy Algorithm / 높은 숫자의 카드가 이기는 게임

문제링크

https://www.codetree.ai/missions/8/problems/a-high-number-of-cards-wins?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 내(A)가 상대편(B)의 카드를 알고 있는 상황. 이 상황에서 내가 상대편(B)를 최대한 이길려면 어떻게 해야하는가?
• B를 이기려면 B가 가진 카드보다 큰값을 제시해야한다. 우선 정렬은 하는게 훨씬 낫다. 정렬이 정답 유무에 미치지 않기 때문이다.
• 핵심!! B의 각 카드보다 크면서 내가 가진 카드들이 몇 개인지 후보 파악을 해야함. → memo
  • B가 1, 4, 6 을 가지고 있다. 
  • 1보다 큰 숫자. 6 - 1 = 5개 존재...1뒤에 존재하는 숫자들은 card_A에 존재하지 않기 때문에 -2를 해야한다.
  • 2 * n - card_B[i] - (n - (i + 1))..B의 각 카드보다 크면서 card_A에 존재하는 값들이 기록된다.
  • memo에 기록되는 숫자의 의미는 memo[i]는 card_B[i]의 값보다 크고 내(A)가 가지고 있는 카드의 수이다. 위의 예를 보면 1, 4, 6의 경우 6은 최대이므로 갖은 카드의 수는 0이다. 4의 경우 5가 있으므로 1이고, 1의 경우 2, 3, 5가 있으므로 3이다.
  • memo = [3, 1, 0]
• 핵심2!! B의 큰값부터 제거를 해야한다.
  • B가 가진 카드가 클수록 내가 낼 수 있는 후보군의 숫자는 적어진다. 그러므로 상대편의 큰 숫자부터 제거를 해서 내가 낼 수 있는 후보군을 많이 확보하면 더 많은 점수를 얻을 수 있다.
  • 주의해야할 점은 내가 상대방 카드를 제거할 때 내 카드도 같이 제거가 된다. 그래서 특정한 시점에서는 이길 수 없는 상황이 발생하게 된다.
• 예시) n = 20인 상황

card_B = [6, 7, 8, 11, 14, 16, 17, 20, 21, 23, 24, 25, 26, 27, 28, 30, 32, 33, 34, 36]

memo = [15, 15, 15, 13, 11, 10, 10, 8, 8, 7, 7, 7, 7, 7, 7, 6, 5, 5, 5, 4]

15	15	15	13	11	10	10	8	8	7	7	7	7	7	7	6	5	5	5	4
15	14	13	12	11	10	9	x	8	x	x	x	x	7	6	5	4	3 사용	2 사용	1 사용
14	13	12	11	10	9	8	8	7	7	7	7	7	6	5	4	3	2	1	0 상태

• 내가 사용할 수 있는 카드의 수(memo에 기록된 값) > user_card_count...점수를 획득할 수 있다!

2. 코드(Python)

n = int(input())
card_b = [int(input()) for _ in range(n)]
# 이 문제는 정렬 상관없다. 그러므로 정렬하고 시작
card_b.sort()

# 나보다 큰 card_a의 후보군
# 1 4 6
# 1 (2, 3, 5) = 2 * 3 - 1 - 2(내 뒤에 있는 애들 제외)
# 2 * n - card_b[i] - (n - i - 1) 
# memo에는 B를 이길 수 있는 개수를 기록!
memo = [0 for _ in range(n)]
for i in range(n):
    memo[i] = 2 * n - card_b[i] - (n - i - 1)

# 상대편의 가장 큰 값부터 제거 - 상대편의 큰값을 먼저 제거해야 내 입장에 유리해짐! 작은 숫자에서 이길 수 있는 후보군들이 많아짐!
# 핵심!! 우리가 가진 가장 큰 카드도 죽기 때문에 중간에 반드시 지는 경우가 존재함! 즉, 중간중간에 카드를 내
# 사용한 카드수를 기록해야한다.
# 나보다 큰 값 - 뽑을 수 있는 카드의 수(memo[idx])> 사용한 카드의 수(used)
used_card_num = 0
score = 0
for idx in range(n - 1, -1, -1):
    if memo[idx] > 0 and memo[idx] > used_card_num:
        score += 1
        used_card_num += 1

print(score)

 

---

# 변수 선언 및 입력:
n = int(input())
a_cards = []
b_cards = [
    int(input())
    for _ in range(n)
]
# b 카드 숫자로 이루어진 hashset을 완성해줍니다.
b_set = set(b_cards)

# a 카드를 완성해줍니다.
a_cards = [
    num
    for num in range(1, 2 * n + 1)
    if num not in b_set
]

# a, b 카드 목록을 전부 오름차순으로 정렬해줍니다.
a_cards.sort()
b_cards.sort()

# a의 카드를 작은 숫자부터 보며
# b카드의 앞에서부터 이길 수 있는 순간에 둘을 매칭하는게 최선임을 이용합니다.
ans = 0
b_idx = 0
for a_idx in range(n):
    # a가 현재 b 카드보다 우세하다면
    # 둘을 매칭해주는게 항상 유리합니다.
    if b_idx < n and a_cards[a_idx] > b_cards[b_idx]:
        ans += 1
        b_idx += 1

print(ans)