문제 소개
원래 집합 S에는 1부터 n까지의 숫자가 모두 포함되어 있다고 가정해 봅시다. 그런데 안타깝게도 어떤 오류 때문에 집합의 한 숫자가 다른 숫자 자리에 복제되어 들어갔고, 그 결과 한 숫자는 두 번 나타나고 다른 한 숫자는 사라지고 말았습니다.
오류가 발생한 이후의 집합 상태를 나타내는 배열 nums가 주어졌을 때, 우리의 과제는 두 번 등장하는 숫자와 빠진 숫자를 각각 찾아 배열 형태로 반환하는 것입니다.
예를 들어 입력이 [1, 2, 3, 4, 4, 6]이라면 출력은 [4, 5]가 됩니다. 여기서 4는 중복된 숫자이고, 5는 빠진 숫자입니다.
해결 접근 방법
이 문제는 부호 마킹(sign marking) 기법과 수학적 합계 공식을 조합하면 추가 배열 없이도 O(n) 시간 복잡도로 해결할 수 있습니다. 전체 흐름은 다음과 같습니다.
- 크기가 2인 배열 v를 정의합니다. (v[0]: 중복 숫자, v[1]: 빠진 숫자)
- s1 := 배열 A의 모든 원소의 합
- n := 배열 A의 크기
- exp_sum := (n × (n + 1)) / 2 → 1부터 n까지의 기대 합계
- i를 0부터 n−1까지 1씩 증가시키며 반복합니다.
- A[|A[i]| − 1] > 0이면, 해당 위치의 값을 음수로 뒤집어 방문 표시를 합니다.
- 그렇지 않다면(이미 음수라면), |A[i]|가 중복 숫자이므로 v[0]에 저장하고 반복문을 빠져나옵니다.
- v[1] := v[0] − (s1 − exp_sum)으로 빠진 숫자를 계산합니다.
- v를 반환합니다.
동작 원리 살펴보기
배열의 각 값은 1부터 n 사이의 숫자이므로, 그 값 자체를 인덱스로 활용할 수 있습니다. 특정 값이 처음 등장하면 대응되는 인덱스의 원소를 음수로 만들어 "이미 본 적 있는 값"이라는 표시를 남깁니다. 어떤 값이 두 번째로 등장했을 때 대응 인덱스의 값이 이미 음수라면, 그 값이 곧 중복된 숫자입니다.
빠진 숫자는 합계의 차이를 이용해 구합니다. 실제 합계(s1)와 기대 합계(exp_sum)의 차이는 '중복 숫자 − 빠진 숫자'와 정확히 같습니다. 따라서 중복 숫자를 먼저 찾았다면, 빠진 숫자는 아래 식으로 간단히 계산할 수 있습니다.
빠진 숫자 = 중복 숫자 − (s1 − exp_sum)
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> findErrorNums(vector<int>& A) {
vector<int> v(2);
long long int s1 = accumulate(A.begin(), A.end(), 0);
int n = A.size();
long long int exp_sum = (n * (n + 1)) / 2;
for (int i = 0; i < n; i++) {
if (A[abs(A[i]) - 1] > 0) {
A[abs(A[i]) - 1] = -A[abs(A[i]) - 1];
}
else {
v[0] = abs(A[i]);
break;
}
}
v[1] = v[0] - (s1 - exp_sum);
return v;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,4,6};
print_vector(ob.findErrorNums(v));
}
입력
{1,2,3,4,4,6}
출력
[4, 5]
실행 결과 첫 번째 요소 4는 두 번 나타난 숫자이고, 두 번째 요소 5는 집합에서 사라진 숫자입니다. (출력 함수가 마지막 요소 뒤에도 쉼표를 붙이기 때문에 화면에는 [4, 5]처럼 표시됩니다.)