n개의 요소로 구성된 배열이 있다고 가정해 보겠습니다. 일부 요소는 두 번 나타나고, 어떤 요소는 한 번만 나타납니다. 모든 요소는 1 ≤ A[i] ≤ n 범위 안에 있습니다. 우리가 찾아야 할 것은 바로 이 배열에 존재하지 않는 숫자들입니다. 단, 추가 공간을 사용하지 않고 O(n) 시간 안에 문제를 해결해야 한다는 제약 조건이 있습니다.
예를 들어 배열이 [4, 3, 2, 7, 8, 2, 3, 1]이라면 결과는 [5, 6]이 됩니다.
해결 접근 방법
이 문제는 인덱스 마킹(index marking) 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 값 v가 배열에 등장했다면, 인덱스 v-1 위치의 값을 음수로 바꿉니다. 모든 순회가 끝난 후에도 양수로 남아 있는 위치 i가 있다면, 그것은 숫자 i+1이 배열에 한 번도 등장하지 않았다는 의미입니다. 부호만 변경하므로 추가 메모리가 전혀 필요 없으며, 배열을 두 번 순회하므로 시간 복잡도 역시 O(n)입니다.
구체적인 단계는 다음과 같습니다.
- 배열의 크기를 n으로 정의합니다.
- i를 0부터 n-1까지 반복합니다.
- x := |A[i]| - 1
- A[x] > 0이면 A[x] := -A[x]로 설정합니다.
- 정답을 담을 배열을 정의합니다.
- i를 0부터 n-1까지 다시 반복합니다.
- A[i] > 0이면 i + 1을 정답 배열에 추가합니다.
- 정답 배열을 반환합니다.
예제 코드
다음 C++ 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]";
}
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& v) {
int n = v.size();
for(int i = 0;i < n; i++){
int x = abs(v[i]) - 1;
if(v[x] > 0) v[x] = -v[x];
}
vector <int> ans;
for(int i = 0; i < n; i++){
if(v[i]>0)ans.push_back(i+1);
}
return ans;
}
};
main(){
Solution ob;
vector<int> v{4,3,2,7,8,2,3,5};
print_vector(ob.findDisappearedNumbers(v));
}입력
[4,3,2,7,8,2,3,5]
출력
[1, 6]
위 예제에서 배열의 크기는 8이며, 실제로 등장하는 값은 2, 3, 4, 5, 7, 8입니다. 따라서 배열에 존재하지 않는 숫자인 1과 6이 결과로 출력됩니다. 이 방법은 정렬이나 해시 테이블 없이 원본 배열 자체를 마커로 활용하기 때문에, 공간 복잡도 O(1), 시간 복잡도 O(n)이라는 제약 조건을 모두 만족하는 매우 우아한 해법입니다.