짝을 지을 때 가장 큰 실력 차이 최소화
자바스크립트 코딩테스트 문제로 pairing-greedy 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
사람들을 둘씩 짝지을 때, 가장 차이가 큰 한 쌍의 차이를 가능한 한 작게 만드는 문제입니다.
문제 설명
정수 배열 skills가 주어집니다. 각 원소는 한 사람의 실력을 뜻합니다.
모든 사람을 정확히 두 명씩 짝지으려고 합니다. 한 사람이 두 개 이상의 짝에 들어가면 안 되며, 모든 사람은 반드시 한 번씩만 사용해야 합니다.
이때 각 짝의 실력 차이는 두 수의 절댓값 차이입니다.
가능한 모든 짝짓기 중에서 가장 큰 실력 차이가 최소가 되도록 만들었을 때, 그 최소값을 반환하는 minimizeWorstPairGap 함수를 작성하세요.
제한사항
skills의 길이는2이상100,000이하입니다.skills의 길이는 항상 짝수입니다.skills[i]는-1,000,000이상1,000,000이하의 정수입니다.- 반환값은 최적으로 짝지었을 때 생기는 짝 차이의 최댓값입니다.
예시
- 입력:
[1, 3, 6, 19]→ 출력:13(1, 3)과(6, 19)로 묶으면 차이는2,13이어서 최댓값은13입니다.- 예를 들어
(1, 19)와(3, 6)으로 묶으면 최댓값이18이 되어 더 나쁩니다.
- 입력:
[8, 2, 5, 10, 12, 14]→ 출력:3- 정렬하면
[2, 5, 8, 10, 12, 14]입니다. - 인접한 두 사람씩 묶으면
(2, 5),(8, 10),(12, 14)가 되고 차이는3,2,2라서 최댓값은3입니다.
- 정렬하면
- 입력:
[4, 4, 4, 4]→ 출력:0- 모든 짝의 차이를 0으로 만들 수 있습니다.
힌트
- 최종 목표는 차이들의 합이 아니라 최댓값을 줄이는 것입니다.
- 정렬했을 때 멀리 떨어진 사람끼리 묶으면 큰 차이가 생기기 쉽습니다.
- 정렬 후 인접한 사람끼리 묶는 방식이 왜 유리한지 생각해 보세요.
해설
이 문제는 모든 짝의 차이 합을 최소화하는 문제가 아니라, 가장 큰 짝 차이 하나를 가능한 작게 만드는 minimax 문제입니다.
핵심은 배열을 정렬한 뒤 인접한 두 사람끼리 묶는 것입니다.
예를 들어 정렬된 배열에서 a <= b <= c <= d가 있을 때,
(a, b)와(c, d)로 묶는 방식은 큰 점프를 만들지 않습니다.- 반대로
(a, c)나(a, d)처럼 멀리 떨어진 값을 섞으면 최소 한 쌍의 차이가 더 커질 가능성이 생깁니다.
정렬된 상태에서 인접 원소끼리 차례로 묶으면, 각 짝의 차이를 불필요하게 키우지 않으면서 전체 최악 차이를 가장 작게 유지할 수 있습니다.
따라서 풀이 방법은 다음과 같습니다.
skills를 오름차순 정렬합니다.0, 2, 4, ...위치를 보며(skills[i], skills[i + 1])를 한 쌍으로 묶습니다.- 각 쌍의 차이를 계산하면서 그중 최댓값을 갱신합니다.
- 마지막에 그 최댓값을 반환합니다.
정렬에 O(n log n)이 걸리고, 이후 순회는 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.