JavaScript로 배열의 모든 요소를 고유하게 만드는 최소 연산 횟수 구하기

문제 정의

숫자로 이루어진 배열 arr을 첫 번째이자 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다.

여기서 '이동(move)'이란 배열 안에서 임의의 요소 arr[i]를 하나 골라 1만큼 증가시키는 작업을 의미합니다. 함수는 배열 arr의 모든 값을 서로 다르게(고유하게) 만들기 위해 필요한 최소 이동 횟수를 반환해야 합니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

const arr = [12, 15, 7, 15];

그렇다면 출력 결과는 다음과 같아야 합니다.

const output = 1;

출력 설명

중복된 값인 15 중 하나를 16으로 단 한 번 증가시키면 배열의 모든 요소가 고유해지므로, 필요한 최소 이동 횟수는 1입니다.

접근 방법

이 문제는 정렬 기반 그리디(greedy) 알고리즘으로 해결할 수 있습니다. 절차는 다음과 같습니다.

1. 배열을 오름차순으로 정렬합니다.
2. 배열을 순회하면서 현재 요소가 바로 앞 요소보다 크지 않은지 확인합니다.
3. 크지 않다면 현재 요소를 '앞 요소 + 1'로 만들고, 증가시킨 양만큼 이동 횟수에 더합니다.
4. 순회가 끝나면 누적된 이동 횟수를 반환합니다.

배열을 정렬하면 중복되거나 역전된 값들이 인접하게 위치하므로, 각 요소를 최소한으로만 증가시켜도 전체 배열이 엄격하게 오름차순(모든 값이 고유)이 됩니다. 시간 복잡도는 정렬에 의해 지배되며 O(n log n), 공간 복잡도는 O(1)(입력 배열 자체를 수정하는 경우)입니다.

구현 코드

const arr = [12, 15, 7, 15];
const makeUnique = (arr = []) => {
    arr.sort((a, b) => a - b);
    let count = 0;
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] <= arr[i - 1]) {
            const temp = arr[i]
            arr[i] = arr[i - 1] + 1
            count += arr[i] - temp
        };
    };
    return count;
};
console.log(makeUnique(arr));

실행 결과

콘솔에는 다음과 같은 결과가 출력됩니다.

1