1일 1커밋 !

1일 1PS 73일차!

📚 문제

[골드 1] - 대표 선수

💡 풀이 과정

  • 처음에는 투 포인터로 생각했다.
    • 모든 학생을 능력치 순서로 정렬하고 투 포인터로 학생들을 비교했다.
    • 1, 2, 2, 3, 4
      • 정렬된 학생들의 반이 위와 같이 주어진다면 2가 중복되기에 단순한 투포인터로는 모든 반 학생이 1명씩 포함된 경우를 반환하지 못한다.
  • 결국 학생들은 반에서 1명씩 뽑혀야한다. 
    3 4
12 16 67 43
7 17 68 48
14 15 77 54
  • 이미 정렬된 위의 예시에서 각 반별로 가장 작은 능력치 학생을 선별한다.
    • [12, 7, 14] 능력치 차를 구한다.
    • 가장 능력치가 작은 7 학생을 해당 반의 다음 학생으로 교체한다.
    • [12, 17, 14]
    • 다음 12 학생을 교체한다.
    • [16, 17, 14]
  • 해당 과정을 위해 각 반에 대한 인덱스를 따로 저장하고, 학생들의 대표는 minHeap 으로 관리한다.

📌포인트

  • minDiffState = min(minDiffState, max(minHeap)[0] - min(minHeap)[0])
    • 최댓값과 최솟값을 다음과 같이 구했다.
    • 하지만 minHeap[0] 으로 바로 최솟값을 접근할 수 있다.
    • 최댓값은 maxState 로 매번 push 하는 능력치와 비교해 관리한다.
  • students = [sorted(list(map(int, input().split()))) for _ in range(N)]
    • 위 코드로 입력받았으나 각 반의 첫 학생을 minHeap 에 넣어야하기에 두 번 도는 for 문을 하나로 합쳤다.
  • while max(idx) < M:
    • 시간초과의 주범이다.
    • 매번 배열의 max 값을 찾으니 시간초과가 발생한다.
    • 종료 조건은 마지막인 인덱스가 “또” 선택 받았을 경우이므로 내부에서 break 를 걸어야한다.

💻 코드


import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
students = []
minHeap = []
# 반별로 정렬해서 배열로 저장한다.
# minHeap 에 각 반의 첫번째가 자신의 반 번호와 함께 들어간다.
for i in range(N):
    students.append(list(map(int, input().split())).sort())
    heapq.heappush(minHeap, (students[i][0], i))

# 첫번째는 모두 들어갔기에 idx 에 1부터 저장한다.
idx = [1] * N

# maxState 와 능력치 차이를 계산한다.
maxState = max(minHeap)[0]
minDiffState = maxState - minHeap[0][0]

# 최대 N*M 번의 비교가 발생한다.
for i in range(N*M):
    state, index = heapq.heappop(minHeap)

    # 이미 모든 반 선수가 비교된 반이 또 선택되었을 경우
    if idx[index] >= M:
        break

    # maxState 를 업데이트한다.
    maxState = max(maxState, students[index][idx[index]])
    # 능력치가 가장 작은 선수를 교체한다.
    heapq.heappush(minHeap, (students[index][idx[index]], index))

    # 능력치 차이를 검사한다.
    minDiffState = min(minDiffState, maxState - minHeap[0][0])
    idx[index] += 1

print(minDiffState)

업데이트:

댓글남기기

참고