문제 보기 · Level 5 · 2023 현대모비스 알고리즘 경진대회 본선 · 정답률 3% · 푼 사람 164명 (2026-09-30 기준)1
문제
지점 n개의 높이가 주어진다. 지점을 한 줄로 늘어놓는 순서는 마음대로 정할 수 있다. 이웃한 두 지점의 높이 차 가운데 가장 작은 값이 가장 커지도록 늘어놓을 때, 그 값을 돌려준다.
- 2 ≤ n ≤ 200,000
- 높이 1 ~ \(10^9\)
풀이
막히면 한 단계씩 펼친다2. 정렬한 높이를 a[0] ≤ a[1] ≤ … ≤ a[n − 1]로 적는다.
필요한 개념
정렬을 한 뒤, 매개변수 탐색처럼 “높이 차를 모두 D 이상으로 만들 수 있나?”를 묻는다. 그 답이 “정렬한 배열에서 연달아 놓인 몇 개의 폭” 조건으로 정리된다. 조건이 “폭 ≥ D” 꼴이라, 이분 탐색 없이 폭 하나가 바로 답이 된다.
1단계 · 작은 예로 손으로 풀기
- [1, 5, 8]: [5, 1, 8]로 놓으면 차이가 4, 7이라 4다.
- [0, 10, 20, 30]: 작은 절반 {0, 10}과 큰 절반 {20, 30}을 번갈아 [20, 0, 30, 10]으로 놓는다. 차이가 20, 30, 20이라 20이다.
- [1, 3, 3, 3, 6]: 3 세 개는 서로 차이가 0이라 이웃하면 안 된다. 다섯 자리에서 서로 붙지 않는 세 자리는 1, 3, 5번째뿐이다. [3, 1, 3, 6, 3]으로 놓으면 차이가 2, 2, 3, 3이라 2다. 가운데 3은 아래(1)와 위(6) 사이에 낀다.
마지막 예에서 작은 절반과 큰 절반을 번갈아 놓기만 하면 0이 나온다. 홀수 개일 때는 더 따져야 한다.
2단계 · 가장 단순한 방법과 그 속도
순서를 모두 해 보면 n!가지다. n = 12만 돼도 4억 7,900만이 넘는다. n = 20만은 어림없다.
3단계 · 핵심 아이디어
- 질문 바꾸기: “높이 차를 모두 D 이상으로 만들 수 있나?”를 묻는다. D가 작을수록 쉽다. 그래서 되는 D 중 가장 큰 것이 답이다.
- 서로 붙으면 안 되는 무리: 정렬한 배열에서 연달아 놓인 값들의 폭(가장 큰 값 − 가장 작은 값)이 D보다 작으면, 그 값들끼리는 이웃할 수 없다. 한 줄 n자리에서 서로 이웃하지 않는 자리는 많아야 ⌈n/2⌉개다. 자리를 (1, 2), (3, 4), …로 둘씩 묶으면 묶음이 ⌈n/2⌉개다(n이 홀수면 마지막 묶음은 한 자리). 그보다 많이 고르면 비둘기집 원리로 어떤 묶음에 두 자리가 들어가고, 한 묶음의 두 자리는 이웃한다. 그러니 이런 무리는 ⌈n/2⌉개를 넘으면 안 된다.
- n이 짝수(n = 2m): 위 조건은 “연달아 m + 1개의 폭이 모두 D 이상”이다. 이 조건이 맞으면 실제로 놓을 수 있다. 큰 절반 U와 작은 절반 L을 \(U_0, L_0, U_1, L_1, \dots\)로 번갈아 놓는다(\(U_j\) = a[m + j], \(L_j\) = a[j]). \(L_j\)의 이웃은 \(U_j\)와 \(U_{j+1}\)이라 차이가 a[m + j] − a[j] 이상이다. 그래서 답은 a[i + m] − a[i] (i = 0 ~ m − 1)의 최솟값이다.
- n이 홀수(n = 2m + 1): 무리는 m + 1개까지 된다. 하지만 m + 1개짜리 무리는 1, 3, …, 2m + 1번째 자리를 모두 차지해야 한다. 자리가 딱 정해지니, 그런 무리는 둘일 수 없다. 그래서 조건은 “연달아 m + 1개의 폭 a[i + m] − a[i] (i = 0 ~ m) 가운데 D보다 작은 것이 하나 이하”다. 답은 이 폭들 가운데 두 번째로 작은 값이다.
- 홀수일 때 실제로 놓는 법: 폭이 가장 좁은 창 a[t] ~ a[t + m]을 홀수 번째 자리에 큰 것부터 놓는다. 그 사이 짝수 번째 자리에는 창 아래 값 a[t − 1], …, a[0]을 먼저, 이어서 창 위 값 a[2m], …, a[t + m + 1]을 놓는다. 창 아래 값 a[s]의 두 이웃 중 작은 쪽은 a[s + m]이라 차이가 폭 a[s + m] − a[s] 이상이다. 창 위 값 a[r]의 두 이웃 중 큰 쪽은 a[r − m]이라 차이가 폭 a[r] − a[r − m] 이상이다. 두 폭 모두 가장 좁은 창이 아니라 두 번째로 작은 값 이상이다. [1, 3, 3, 3, 6]은 t = 1이라 [3, 1, 3, 6, 3]이 된다.
4단계 · 코드 흐름
- 높이를 정렬하고 m = n // 2로 둔다.
- n이 짝수면 a[i + m] − a[i] (i = 0 ~ m − 1)의 최솟값을 돌려준다.
- n이 홀수면 a[i + m] − a[i] (i = 0 ~ m)를 모아 정렬하고, 두 번째 값을 돌려준다.
5단계 · 파이썬 코드
def solution(heights):
a = sorted(heights)
n = len(a)
m = n // 2
if n % 2 == 0:
return min(a[i + m] - a[i] for i in range(m)) # 연달아 m + 1개의 폭 중 최소
widths = sorted(a[i + m] - a[i] for i in range(m + 1)) # 연달아 m + 1개의 폭
return widths[1] # 하나는 좁아도 된다
a[i + m] - a[i]: a[i]부터 a[i + m]까지 m + 1개의 폭이다.- n이 홀수면 m ≥ 1이라 폭이 2개 이상 있어
widths[1]이 늘 있다. - 실제 배치를 만드는
arrange함수는 코드 파일에 있다. 검증에서 그 배치의 최소 차이가 답과 같은지 본다.
6단계 · 실행 추적
| 높이 | 정렬 | m | 폭 a[i + m] − a[i] | 답 | 배치 |
|---|---|---|---|---|---|
| [11, 6, 4, 11] | [4, 6, 11, 11] | 2 | 7, 5 | 최솟값 5 | [11, 4, 11, 6] |
| [1, 3, 3, 3, 6] | 그대로 | 2 | 2, 0, 3 | 두 번째 2 | [3, 1, 3, 6, 3] |
| [9, 9, 9, 9, 30] | 그대로 | 2 | 0, 0, 21 | 두 번째 0 | — |
마지막 줄은 폭 0인 창이 둘이다. 9 넷 중 둘은 어떻게 놓아도 이웃해서 0이다.
7단계 · 복잡도와 흔한 실수
정렬이 \(O(n \log n)\)이고 나머지는 \(O(n)\)이다. 높이 20만 개를 0.1초 안에 풀었다.
- 홀수일 때 작은 절반과 큰 절반을 번갈아 놓는 두 가지만 본다. [1, 3, 3, 3, 6]에서 0이 나오지만 답은 2다.
- 홀수에도 짝수 공식(폭들의 최솟값)을 쓴다. [1, 5, 8]에서 3이 나오지만 답은 4다.
검증: 문제의 예시 3개, 1단계와 6단계의 값과 배치, 7단계의 두 실수를 코드로 확인했다. 무작위 입력 3,000개(7개 이하)에서 순서를 모두 해 보는 풀이와, 300개(8 ~ 11개)에서 “D가 되는지 비트마스크로 직접 따지는” 풀이와 결과가 같았다. 모든 입력에서 arrange가 만든 배치의 최소 차이도 답과 같았다. 20만 개의 시간도 쟀다 — 21_pg214292_p1.py