[Algorithm] 없는 숫자 찾기

1부터 n까지의 수 집합이 존재한다.
이 중에서 하나의 수만 제외하고 n-1개의 수 집합 중에서 서로 다른 숫자 n-1개를 입력받는다.
여기서 존재하지 않는 숫자는 무엇인가?
ex) n=5 이고 {1,2,4,5} 입력받았다면  답은 "3"이다.
입력 : 5
          1 2 4 5
출력 : 3

크게 두 가지 방법이 존재한다.

 

배열 사용

 

첫 번째는 넉넉한 크기의 배열을 만든 다음에 모두 0을 저장한다.

 

그리고 수를 입력받으면 그 값을 인덱스로 사용하여 배열 해당 인덱스의 값을 1로 저장한다.

 

다 입력받고 나면 0이 들어있는 인덱스를 찾으면 끝이다.

 

위의 예시에서는 수를 전부 입력받으면 아래와 같은 모습이 된다.

 

index	0	1	2	3	4	5
value	0	1	1	0	1	1

0번 인덱스의 값은 사용하지 않고 1번 인덱스부터 조사하면 된다. 평균적으로 n/2번의  조사해야한다.

#include <iostream>
using namespace std;
int main(){
	int arr[1000] = {0,}; //배열을 0으로 초기화 
	int n,temp;
	cin>>n;
	for(int i = 1;i<n;i++){
		cin>>temp;
		arr[temp] = 1; //해당 인덱스의 배열 값을 1로 저장  
	}
	for(int i = 1;i<=n;i++){
		if(!arr[i]){ //arr[i]가 0이라는 것은 i가 입력되지 않았다는 뜻  
			cout<<i;
			return 0;
		}
	}
}

 

이보다 시간을 단축시키는 방법이 존재한다.

덧셈 공식 사용

1부터 n까지 더하는 공식이 $$\frac{n(n+1)}{2}$$ 라는 것은 다들 알고 있을 것이다.

 

그렇다면 먼저 위 공식을 사용하여 1부터 n까지 더한 값을 구한다.

 

그리고 값을 입력받을 때마다 변수에 계속 더해서 입력받은 수의 합을 구한다.

 

그리고 1부터 n까지의 합에서 위의 합을 빼버리면 입력받지 않은 수를 알 수 있다.

#include <iostream>
using namespace std;
int main(){
	int arr[1000] = {0,};
	int n,temp;
	int res= 0; 
	cin>>n;
	for(int i = 1;i<n;i++){
		cin>>temp;
		res+=temp;
	}
	cout<<n*(n+1)/2-res;
}

1번의 계산으로 없는 수를 구할 수 있다.

 

만약 n개 중 n-2개만 입력받고 입력받지 않은 두 수를 구한다면 어떻게 할까?

 

이것도 숫자 하나만 입력받지 않을 때와 비슷하다. 첫 번째 방식인 배열을 사용하면 역시 1이 아닌 인덱스 두 개를  찾기만 하면 된다.

 

두 번째 방식에서는 조금 달라진다.

 

없는 수가 a, b라고 하자. 합 공식을 사용한다면 a+b의 값까지는 구해낼 수 있지만 a와 b의 정확한 값을 구해낼 수 없다.

 

그래서 추가로 1부터 n까지 전부 제곱을해서 합을 구하는 것이다.

 

그리고 입력받은 수를 전부 제곱해서 더한 값을 빼면  $$ a^{2}+b^{2} $$의 값을 알 수 있다.

 

그러면 아래처럼 ab의 값을 구할 수가 있고 $$ (a+b)^{2}-a^{2}+b^{2}=2ab $$

 

아래와 같이 이차 방정식의 근을 구하면 된다. $$ x^{2}-(a+b)x+ab $$