#117 · 투 포인터어려움3-포인터,정렬

세 공장 로트 동기화 검사

문제

부품 제조사 K사는 1공장·2공장·3공장에서 같은 부품을 병렬 생산한다. 각 공장은 생산이 끝난 로트마다 완료 시각(0 이상의 정수, 단위: 분)을 기록하는데, 기록 순서는 뒤죽박죽이라 정렬되어 있지 않다.

품질검사팀은 각 공장에서 로트를 정확히 하나씩 골라 묶음 검사를 진행한다. 세 로트의 완료 시각이 서로 가까울수록 동일한 생산 조건에서 만들어졌을 가능성이 높으므로, 고른 세 완료 시각의 최댓값 − 최솟값(격차)이 최소가 되는 조합을 찾으려 한다.

세 공장의 완료 시각 배열 lots1, lots2, lots3가 주어질 때, 다음을 담은 길이 4의 배열을 반환하는 solution(lots1, lots2, lots3)을 작성하라.

[격차, v1, v2, v3]

v1 ≤ v2 ≤ v3 : 고른 세 완료 시각을 오름차순으로 정렬한 값
격차 = v3 - v1

동률 규칙: 최소 격차를 만드는 조합이 여러 개라면, 세 값을 오름차순으로 정렬한 결과 [v1, v2, v3]가 사전순으로 가장 앞서는 조합을 반환한다. (즉 v1이 작은 쪽, 같으면 v2가 작은 쪽, 같으면 v3가 작은 쪽.)

예시

lots1	lots2	lots3	결과	설명
`[10, 4, 26]`	`[12, 3, 30]`	`[11, 20, 7]`	`[2, 10, 11, 12]`	10·12·11을 고르면 격차 2로 최소
`[1, 5]`	`[2, 6]`	`[3, 7]`	`[2, 1, 2, 3]`	격차 2인 조합이 (1,2,3)과 (5,6,7) 두 개 — 사전순으로 앞서는 `[1,2,3]` 선택
`[100]`	`[40]`	`[75]`	`[60, 40, 75, 100]`	각 공장에 로트가 하나뿐이면 그 조합이 답

제약 조건

1 ≤ lots1.length, lots2.length, lots3.length ≤ 100,000
각 완료 시각은 0 이상 1,000,000,000 이하의 정수
같은 배열 안에 중복된 완료 시각이 있을 수 있다
입력 배열은 정렬되어 있지 않다

시간 복잡도 목표: O(N log N) (N = 세 배열 길이의 합)

테스트 케이스

예시 1: 기본 케이스 — 10·12·11 조합이 격차 2로 최소

입력: lots1 = [10,4,26], lots2 = [12,3,30], lots3 = [11,20,7]

출력: [2,10,11,12]

예시 2: 동률 — (1,2,3)과 (5,6,7) 모두 격차 2, 사전순 앞선 [1,2,3]

입력: lots1 = [1,5], lots2 = [2,6], lots3 = [3,7]

출력: [2,1,2,3]

예시 3: 길이 1 배열 — 조합이 하나뿐

입력: lots1 = [100], lots2 = [40], lots3 = [75]

출력: [60,40,75,100]

중복 값 — 세 공장 모두 8이 존재해 격차 0

입력: lots1 = [8,3,8], lots2 = [8,1], lots3 = [2,8,9]

출력: [0,8,8,8]

서로 다른 배열에 같은 값 5가 존재

입력: lots1 = [5,9], lots2 = [5,14], lots3 = [6,10]

출력: [1,5,5,6]

solution.ts

에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.