[Hackerrank 문제 풀이] Closest Numbers

Junu Kim·2025년 12월 10일

Java hackerrank

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

57/89

[Sort] Closest Numbers

난이도: ★★☆☆☆ • solved on: 2025-12-11

문제 요약

문제 유형: 정렬, 그리디
요구사항:
정수 배열이 주어졌을 때, 절대 차이가 최소인 모든 쌍을 찾아
a1 b1 a2 b2 ... 형식으로 오름차순 정렬된 상태로 출력해야 한다.

사용 개념

자료구조
- List<Integer>: 입력/출력 관리
- ArrayList<Integer>: 결과 쌍 저장
알고리즘/기법
- 정렬(sort) 후 인접 원소 차이만 검사
- 단일 패스(minimum tracking)
핵심 키워드
- 정렬(sorting)
- 최소 거리(minimum difference)
- 인접 쌍(adjacent pair)

풀이 아이디어

1. 핵심 아이디어

배열을 오름차순 정렬한다.
정렬된 상태에서는

“최소 차이를 가지는 두 원소는 항상 인접한 두 원소 중에 있다.”
따라서 arr[i] 와 arr[i+1] 의 차이만 보면 된다.
첫 번째 인접 쌍으로 minDistance 를 초기화한 뒤,
- 더 작은 차이를 만나면 → 결과 리스트를 비우고 새 쌍만 저장
- 같은 차이를 만나면 → 결과 리스트에 해당 쌍을 추가

2. 로직 흐름 (의사코드)

정렬(arr)

minDistance = arr[1] - arr[0]
result = [arr[0], arr[1]]

for i from 1 to n-2:
    currentDistance = arr[i+1] - arr[i]
    if currentDistance < minDistance:
        result.clear()
        result.add(arr[i])
        result.add(arr[i+1])
        minDistance = currentDistance
    else if currentDistance == minDistance:
        result.add(arr[i])
        result.add(arr[i+1])

return result

정렬했기 때문에 arr[i+1] - arr[i] 는 항상 0 이상이어서 Math.abs 없이 그대로 사용 가능하다.

코드

public static List<Integer> closestNumbers(List<Integer> arr) {
    List<Integer> result = new ArrayList<>();
    arr.sort((a, b)->{
        return a.compareTo(b);
    });
    int minDistance = 0;
    for(int i = 0; i < arr.size(); i++){
        if(i == arr.size()-1) break;
        if(i == 0){
            minDistance = arr.get(i+1) - arr.get(i);
            
            result.add(arr.get(i));
            result.add(arr.get(i+1));
            
            continue;
        }
        
        int currentDistance = arr.get(i+1) - arr.get(i);
        if(currentDistance < minDistance){
            
            result.clear();
            
            result.add(arr.get(i));
            result.add(arr.get(i+1));
            
            minDistance = currentDistance;
            continue;
        }
        if(currentDistance == minDistance){
            
            result.add(arr.get(i));
            result.add(arr.get(i+1));
        }
    }
    return result;
}

시간·공간 복잡도

시간 복잡도:
- 정렬: O(N log N)
- 한 번 순회: O(N)
  → 전체: O(N log N)
공간 복잡도:
- 입력 외에 결과 저장용 result 만 사용 → O(K) (K는 답으로 나오는 원소 개수)

어려웠던 점

처음에는 minDistance 를 적절히 설정해 놓고 반복문에서 값을 갱신하지 않아서 문제가 발생했다.
minDistance 를 언제, 어떤 값으로 초기화할지에 대한 감이 부족하면
조건문이 맞아도 전체 로직이 동작하지 않는 경우가 많다.

배운 점 및 팁

최소값/최댓값 관리 패턴
- 보통은
```
int min = Integer.MAX_VALUE;
for (...) {
    min = Math.min(min, value);
}
```
  같이 “절대 이길 수 없는 값”으로 초기화한 뒤, 반복문에서만 갱신하는 패턴이 깔끔하다.
정렬 후 인접 원소만 보는 패턴은
- 최소/최대 차이, 최소 간격, 가장 가까운 값 찾기 등 여러 문제에서 재사용된다.