유일한 수 두개

알고리즘 문제 전체 링크

 

judge.koreatech.ac.kr/problem.php?id=1074

 

 

유일한 수 문제의 응용 버전이다.

 

모든 수가 짝이 있으나 단 2개의 수만 짝이 없다.

유일한 수 문제대로 풀면 짝이 있는 수는 자연스럽게 제거할 수 있지만,

짝이 맞지 않는 두 수가 xor 연산되어 있어서 답을 구할 수 없게 될 것 같다.

 

하지만 여전히 xor 연산을 이용해서 문제를 해결할 수 있다.

 

먼저 두 수가 다르다는 것은, 최소 1 bit가 다르다는 뜻이 된다.

 

즉, 모든 N을 xor한 후, 어떤 다른 1 bit를 기준으로

1 bit가 있는 경우는 on에 xor을

1 bit가 없는 경우는 off에 xor을 하면

 

두 수가 분리된다.

 

예를 들어서 두 수가 3과 7이라고 하자.

0011(3)과 0111(7)의 xor은 0100이 된다.

 

0100 비트가 있는 곳은 on에 xor하면 on = 7이 된다.

반대로 0100이 없는 곳은 반드시 off = 3이 된다.

 

3과 7외에는 모든 수가 짝이 맞기 때문에, 0100 비트가 있으나 없으나 자연스레 제거되기 때문이다.

 

이제 다른 두 수의 xor 연산 중 1 bit만 남기는 방법만 알면 된다.

여기에서는 편하게 최하위 또는 최상위 비트를 구하면 된다.

 

최하위 비트를 구하는 방법이 더 간단하므로. 아래의 코드를 참고하자.

#include <stdio.h>

int T, N;
int A[100200];

int main(void)
{
	scanf("%d", &T);

	for (int tc = 0; tc < T; tc++)
	{
		int all, on, off, lsb;
		
		all = on = off = 0;

		scanf("%d", &N);

		for (int i = 0; i < N; i++)
		{
			scanf("%d", &A[i]);
			all ^= A[i]; /* 모든 수를 xor 연산하면 남은 두 수만 xor이 된다 */
		}

		lsb = all & (-all); /* 최하위 bit를 구하고 */

		for (int i = 0; i < N; i++) 
		{
			if (A[i] & lsb) on ^= A[i]; /* 해당 bit가 있다면 on에 xor 누적 */
			else off ^= A[i]; /* 없다면 off에 xor 누적 */
		}

		if (on < off) printf("%d %d\n", on, off); /* 작은 것부터 출력 */
		else printf("%d %d\n", off, on);
	}

	return 0;
}

---

마찬가지로, msb를 구하는 방법으로도 문제를 풀 수 있다.

lsb를 구하는 것보다 조금 복잡하기 때문에 약간 느려진다.

그리고 음수가 포함되기 때문에 비트의 최상단이 1인지 체크하는 코드가 필요하다.

n + 1에 의해 오버플로우가 발생하기 때문이다.

#include <stdio.h>

int T, N;
int A[100200];

unsigned int getMsb(unsigned int n)
{
	if (n & (1 << 31)) return (1 << 31); /* 음수의 경우 */

	n |= n >> 1;
	n |= n >> 2;
	n |= n >> 4;
	n |= n >> 8;
	n |= n >> 16;

	n = n + 1;

	return (n >> 1);
}

int main(void)
{
	scanf("%d", &T);

	for (int tc = 0; tc < T; tc++)
	{
		int all, on, off, msb;
		
		all = on = off = 0;

		scanf("%d", &N);

		for (int i = 0; i < N; i++)
		{
			
			scanf("%d", &A[i]);
			all ^= A[i];
		}

		msb = getMsb(all);

		for (int i = 0; i < N; i++) 
		{
			if (A[i] & msb) on ^= A[i];
			else off ^= A[i];
		}

		if (on < off) printf("%d %d\n", on, off);
		else printf("%d %d\n", off, on);
	}

	return 0;
}