정수 배열 A가 주어졌다고 가정해 봅시다. 여기서 '한 번의 이동(move)'이란 배열의 임의의 원소 A[i]를 선택하여 1만큼 증가시키는 연산을 의미합니다. 우리의 목표는 배열 내 모든 값이 서로 중복되지 않도록(고유하게) 만드는 데 필요한 최소 이동 횟수를 구하는 것입니다.
예를 들어 입력이 [3, 2, 1, 2, 1, 7]이라면 출력은 6입니다. 총 6번의 이동 후 배열은 [3, 4, 1, 2, 5, 7]이 될 수 있으며, 5번 이하의 이동으로는 모든 값을 고유하게 만드는 것이 불가능함을 알 수 있습니다.
문제 해결 접근 방식
이 문제는 정렬(Sorting)과 그리디(Greedy) 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열을 오름차순으로 정렬하면, 중복되거나 역전된 값들을 왼쪽에서 오른쪽으로 순차적으로 처리할 수 있습니다.
- 현재 원소가 이전 원소보다 작거나 같다면, 두 값이 겹치지 않도록 현재 원소를 '이전 원소 + 1'로 만들어야 합니다.
- 이때 필요한 증가량(이전 원소 + 1 − 현재 원소)을 결과값에 누적합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 결과를 저장할 변수
ret을 0으로 초기화합니다. - 배열 A를 오름차순으로 정렬합니다.
- 인덱스 1부터 배열의 끝까지 순회하면서, 만약
A[i] <= A[i-1]이라면ret += (A[i-1] + 1) - A[i]를 수행하고A[i] = A[i-1] + 1로 갱신합니다. - 순회가 끝나면
ret을 반환합니다.
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드 (C++)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int ret = 0;
sort(A.begin(), A.end());
for(int i = 1; i < A.size(); i++){
if(A[i] <= A[i - 1]){
ret += (A[i - 1] + 1) - A[i];
A[i] = A[i - 1] + 1;
}
}
return ret;
}
};
main(){
vector<int> v1 = {3,2,1,2,1,7};
Solution ob;
cout << (ob.minIncrementForUnique(v1));
}입력
[3,2,1,2,1,7]
출력
6
동작 과정 살펴보기
입력 [3, 2, 1, 2, 1, 7]을 정렬하면 [1, 1, 2, 2, 3, 7]이 됩니다. 이후 순회 과정은 다음과 같습니다.
- i=1: A[1]=1 ≤ A[0]=1 → A[1]을 2로 만들고, 비용 1 추가 → ret=1
- i=2: A[2]=2 ≤ A[1]=2 → A[2]를 3으로 만들고, 비용 1 추가 → ret=2
- i=3: A[3]=2 ≤ A[2]=3 → A[3]을 4로 만들고, 비용 2 추가 → ret=4
- i=4: A[4]=3 ≤ A[3]=4 → A[4]를 5로 만들고, 비용 2 추가 → ret=6
- i=5: A[5]=7 > A[4]=5 → 변경 없음
최종적으로 배열은 [1, 2, 3, 4, 5, 7]이 되고, 총 이동 횟수는 6입니다.
복잡도 분석
- 시간 복잡도: O(N log N) — 정렬에 지배적으로 영향을 받습니다.
- 공간 복잡도: O(1) — 입력 배열 외에 추가 공간을 거의 사용하지 않습니다.