[그리디] Greedy Algorithm / 자연수 M/2개의 쌍

문제링크

https://www.codetree.ai/missions/8/problems/m2-pairs-of-natural-numbers?&utm_source=clipboard&utm_medium=text

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

1. 핵심

• 합들 중 최댓값이 최소가 되도록 하려면 가장 작은 수와 가장 큰 수를 순서대로 매칭하면 된다.
• 방법1(메모리초과 + 시간초과)
  • 각 값들을 max_heap, min_heap에 넣어서 m // 2만큼 max_q + min_q의 조합하고 조합한 것 중 최대값을 고른다.
  • 문제는 m이 10억이므로 최대값을 갱신하는 과정 중에 최대 5억번 for문을 돌며 ▷ 시간 초과
  • 최대 10억개의 숫자를 heap에 넣으려고 하니까 ▷ 메모리 초과
  • 따라서, m의 범위가 작았다면 heap으로 할 수 있지만 m의 범위가 너무 크기 때문에 heap은 불가능하다.
• 방법2(시간초과)
  • 결국 가장 작은 값과 가장 큰 값을 매칭시키는 것이 포인트이다. 그러다가 가진 수만큼을 사용하면 더 이상 더하기를 해서는 안되는 데 이를 파악하기 위해서 deque 자료를 사용했다.
  • 값으로 정렬하면 deque([1, 2], [2, 5], [1, 8])이 있을 때
    • 가장 큰 값과 가장 작은 값을 매칭해야하므로 first = 0, last = -1 로 가장 처음 원소와 가장 마지막 원소를 가르키도록 한다.
    • 이후 2과 8이 쓰이면 -1, -1을 해서 dq가 빌 때까지 while문을 돌았다.
  • 문제는 사용 후 하나씩 제거하기 때문에 deque([1000000000, 2], [2, 5], [1000000000, 8]), 2와 8이 10억개 있으면 10억번을 전부 돌아야한다.
• 방법3(시간초과)
  • 방법2의 문제점은 10억번을 모두 돌아서 발생했다. 그러므로 우리는 한 번에 쌍을 만들 수 없을까?
  • deque([8, 2], [2, 5], [5, 8]) 2가 8개, 8이 5개 존재한다. 만들 수 있는 쌍의 수는  min(8, 5)이다.
  • 따라서 -1씩 빼는게 아니라 min값을 빼서 만들어진 쌍을 한 번에 제거하도록 한다.
• 방법4(해결)
  • 그런데, 또 시간초과가 났다. 왜그럴까?
  • deque([1, 2], [2, 5], [1, 8]) 이 예시를 보면 2와 8이 매칭되고 5가 2개만 남은 상황이다. 그래서 1번 매칭이 된다. 그런데 deque([10000000000, 5]) 이렇게 되면 방법3에서 min값으로 한 번에 쌍을 제거하는 방법이 통하지 않는다.
  • 그런데 deque에 원소가 1개만 남게 되면 사실 남은 숫자 * 2 만 해도 된다. 그 이상을 할 필요는 없다. 어짜피 10만 나올테니까
  • 그래서 그 부분을 예외처리하면 문제가 풀리게 된다.

2. 코드(Python)

# 두 집합의 차이가 적은 것을 찾아야함
# 8 7 6 2
# (최대, 최소)로 구성
# 총합을 m/2로 만들어야하는데 최대값이 최소를 만들기 위해서 최대, 최소로 구성해서 각 쌍의 차이를 최소화 시키는게 최대화를 시킬 수 있을 것 같음

from collections import deque

t = int(input())

arr = []
for _ in range(t):
    x, y = map(int, input().split())
    arr.append([x, y])
# 값으로 정렬, 오름차순
arr.sort(key=lambda x: x[1])
dq = deque(arr)

first = 0
last = -1
ans = 0
while dq:
    if dq[first][0] == 0:
        dq.popleft()

    if not dq:
        break

    if dq[last][0] == 0:
        dq.pop()

    #  쌍을 이룰 수 있는 경우 쌍의 개수만큼 제거!
    # (2, 8) - (4, 1) 이라고 했을 때 최대2개까지 생성 가능하므로 min(2, 4)만큼 제거
    # 문제는 dq에 숫자 종류가 1개만 남을 경우 남은 숫자 * 2만 해도 된다. 어짜피 2 * 숫자만 나올 것이므로!
    if len(dq) == 1:
        ans = max(ans, dq[first][1] * 2)
        break

    ans = max(ans, dq[first][1]+ dq[last][1])
    k = min(dq[first][0], dq[last][0])
    dq[first][0] -= k
    dq[last][0] -= k

print(ans)