[코드트리] Greedy - 높은 숫자의 카드가 이기는 게임

코드트리 네이버 커리큘럼 - Greedy Algorithm

• 높은 숫자의 카드가 이기는 게임 (Python)
  https://www.codetree.ai/cote/14/problems/a-high-number-of-cards-wins/description

Code

N = int(input())
B_cards = list(int(input()) for _ in range(N))

all_cards = list(i for i in range(1, 2*N+1))

A_cards = []
# in을 안쓰고 A의 카드 리스트를 채우려고 시도했으나... 실패
# b = 0
# for i in range(2*N):
#     if(len(A_cards) == N):
#         break
#     if(all_cards[i] == B_cards[b] and b < N):
#         b += 1
#     else:
#         A_cards.append(all_cards[i])
#         continue

b_set = set(B_cards)        # in 연산의 시간초과 해결을 위하여 set로 변경

for i in range(len(all_cards)):
    if(all_cards[i] not in b_set):
        A_cards.append(all_cards[i])

A_cards.sort()      # 정렬해서 오름차순으로 비교해야 최댓값을 구할 수 있음
B_cards.sort()

ans = 0
j = 0

for i in range(N):
    if (A_cards[i] > B_cards[j] and j < N):     # 현재 A의 카드가 B를 이긴다면 -> 정답 추가, 다음 B의 카드 비교
        ans += 1
        j += 1

print(ans)

풀이 및 해설

• 처음에는 B의 카드에 순서는 정해져있는줄 알았으나 예제를 확인했을 때 아니라고 판단
• 테케에서 틀린 시간 초과 해결에 애를 먹었다.
  • A가 들고있는 카드를 구하는 과정에서 in 연산을 사용하였는데 O(N^2) 연산이라 실패
  • 이에 set으로 B를 따로 선언해주고 set을 사용하여 in 연산 실행
  • https://kyleyj.tistory.com/56 → set은 in 연산에 O(1) 시간이 걸림
• 정렬 → 오름차순 비교 → 현재 A의 카드가 B보다 크다면 정답으로 추가
  • B의 카드 인덱스 조정을 위해 for문은 A의 인덱스를 조작하는 것 하나 아래에서 B의 인덱스는 변수로 컨트롤
  • 두 카드의 인덱스를 동일시하며 이동하면 최댓값을 구할 수 없다.