Medium - Solving Algorithmic Problems; Find a Duplicate in an Array
in Trend
Trend 파악을 위한 Medium 기고문 포스팅 - 알고리즘 문제 풀기: 배열안에 중복찾기
이 포스트는 알고리즘 문제 풀기 시리즈 중 하나입니다. 많은 알고리즘 관련 포스트들은 그냥 해답에 대한 설명만 합니다. 그렇기 때문에 실제로 효율적은 해답에 다다를 수 있도록 한줄 한줄 이해하는 것이 쉽지 않습니다. 그렇기 때문에 이 시리즈의 목표는 문제를 해결하는 잠재적인 프로세스를 묘사하는 것입니다.
Problem
- 배열 안에 중복된 값 찾기
n + 1 크기의 배열이 있고 값은 1과 n 사이의 정수이다. 중복된 것을 찾으시오, 중복된 값이 여러개 있을 경우 그중 하나를 리턴하고 중복이 없다면 -1을 리턴하시오
Example:
Input: [1, 2, 2, 3]
Output: 2
Input: [3, 4, 1, 4, 1]
Output: 4 or 1
Solving Process
정답에 대해서 얘기하기 전에 먼저 문제에 대해서 조금 얘기해 봅시다. 1 ~ n 범위의 정수를 가진 n+1 크기의 배열을 가지고 있습니다. 예를들어 배열의 크기가 5라면 해당 배열은 1 ~ 4까지 값을 가지고 있을 것입니다. 이 말은 최소한 한개는 중복이 된다는 말입니다. 유일한 예외는 배열의 사이즈가 1인 경우인데 이때만 -1을 리턴하면 됩니다.
Brute Force
for i = 0; i < size(a); i++ {
for j = i+1; j < size(a); j++ {
if(a[i] == a[j]) return a[i]
}
}
브루트포스 방법으로 구현하기 위해서는 두개의 포문이 필요합니다. O(n^2)의 시간 복잡도와 O(1)의 공간 복잡도를 가집니다.
Count Iterations
또 다른 방법은 각 정수에 대해 순회하는 횟수를 가지는 자료구조를 사용하는 것입니다. 이 방법은 배열이나 해시테이블을 사용해서 구현할 수 있습니다.
public int repeatedNumber(final List<Integer> list) {
if(list.size() <= 1) {
return -1;
}
int [] count = new int[list.size() - 1];
for(int i = 0; i < list.size(); i++) {
int n = list.get(i) - 1;
count[n]++;
if (count[n] > 1) {
return list.get(i);
}
}
return -1;
}
인덱스 i의 값은 i+1 숫자의 중복횟수를 나타냅니다. 이 방식은 O(n)의 시간복잡도와 O(n)의 공간복잡도를 가집니다
Sorted Array
단순화 기법을 적용한다면 정렬된 배열을 사용하여 정답을 찾을 수 있습니다. 이 경우에는 그냥 각 요소를 오른쪽의 인접한 요소와 비교합니다.
public int repeatedNumber(final List<Integer> list) {
if (list.size() <= 1) {
return -1;
}
Collections.sort(list);
for (int i = 0; i < list.size() - 1; i++) {
if (list.get(i) == list.get(i + 1)) {
return list.get(i);
}
}
return -1;
}
O(1)의 공간복잡도를 가지지만 정렬을 해야하기 때문에 O(nlog(n))의 시간복잡도를 가집니다.
Sum of the Elements
우리가 생각해 볼 수 있는 다른 방법은 배열의 요소들의 값을 더하고 1 + … + n까지의 합과 비교하는 것입니다.
Input: [1, 4, 3, 3, 2, 5]
Sum = 18
n = 5,
1 + 2 + 3 + 4 + 5 = 15
=> 18 - 15 = 3, 중복된 수는 3
이 예제에서는 O(n)의 시간 복잡도와 O(1)의 공간 복잡도를 가지지만 하나의 중복된 수가 있을 때만 동작합니다. 반례를 살펴보겠습니다.
Input: [1, 2, 3, 2, 3, 4]
Sum = 15
n = 5,
1 + 2 + 3 + 4 + 5 = 15
=> Not Working
Maker
말씀드리고 싶은 재밌는 방법이 있습니다. 지금까지의 해법들은 1과 n사이의 정수라는 사실을 이용하지 않았습니다. 이런 흥미로운 제약조건 때문에 각 값들은 배열에서 일치하는 인덱스가 있습니다. 해당 해법은 이 배열을 마치 링크드 리스트처럼 취급하는 것입니다.
Example with [2, 3, 3, 1]
모든 요소를 순회하며 일치하는 마킹의 값으로 인덱스에 플래그를 마이너스 값으로 변경합니다. 만약 마킹된 값이 이미 마이너스라면 해당 인덱스가 중복이라는 뜻입니다.
public int repeatedNumber(final List<Integer> list) {
if (list.size() <= 1) {
return -1;
}
for (int i = 0; i < list.size(); i++) {
if(list.get(Math.abs(list.get(i))) > 0) {
list.set(Math.abs(list.get(i)), -1 * list.get(Math.abs(get(i))))
} else {
return Math.abs(list.get(i))
}
}
return 0;
}
O(n)의 시간 복잡도와 O(1)의 공간복잡도를 가집니다. 그러나 입력된 리스트의 가변성을 요구합니다.
Runner Technique
주어진 배열을 연결 리스트처럼 고려해서 문제를 접근하는 또다른 방법이 있습니다. (이게 가능한 이유는 제약조건에 각 정수들이 1과 n사이의 값이기 때문입니다.)
Example with [1, 2, 3, 4, 2]
간단하게 사이클이 존재하는 경우 중복이 있다고 단순화 시킬 수 있고 중복은 사이클의 시작점 입니다. Floyd의 사이클 찾기 알고리즘을 사용해서 다음과 같은 알고리즘을 구현할 수 있습니다.
- slow와 fast라는 두개의 점을 만듭니다
- 각 단계마다 slow는 한번, fast는 두번을 움직입니다.
- slow == fast 일때 우리는 사이클에 있습니다.
public int repeatedNumber(final List<Integer> list) {
if (list.size() <= 1)
return -1;
int slow = list.get(0);
int fast = list.get(list.get(0));
while (fast != slow) {
slow = list.get(slow);
fast = list.get(list.get(fast));
}
slow = 0;
while (fast != slow) {
slow = list.get(slow);
fast = list.get(fast);
}
}
이 방법은 O(n)의 시간 복잡도와 O(1)의 공간 복잡도를 가지고 있으며 인풋 리스트의 가변성을 요구하지 않습니다.
Summary
- 배열에서 중복된 값을 찾아내는 알고리즘
