[CodeGround] Practice - 숫자 골라내기

문제

초등학교교 학생인 정우와 석환이는 최근 학교에서 두 이진수의 XOR 연산에 대해 배웠다.
 둘은 매우 영특한 학생이라 새로 배운 연산을 갖고 이리저리 장난치기 시작했다.
 다만 석환이는 정우에게 일을 시키는 것을 좋아하는지라 다음과 같은 제안을 했다.

“내가 N개의 10진수를 주면, 등장하는 숫자들 중 홀수번만 나타나는 숫자들을 모두 XOR한 결과를 구해줘.”

예를 들어 '2, 5, 3, 3' 이 주어질 경우, '2'와'5'는 1번(홀수 번) 나타나고 '3' 은 2번 (짝수 번) 나타나므로
홀수 번 나타난 '2' 와 '5'를 XOR 한 결과를 구해야 하고,
'2, 5, 3, 3, 2, 4, 5, 3' 이 주어질 경우 '2' 와 '5' 는 2번 나타나고, '3' 은 3번, '4' 는 1번 나타나므로
홀수 번 나타난 '3' 과 '4'를 XOR 한 결과를 구해야 한다.

정우는 제안을 수락했지만, 가면 갈수록 매번 XOR 연산을 수행하는 일에 지치고 있다.
정우를 도와서 주어 진 문제를 해결하는 프로그램을 작성하라.

- 제한시간: 전체 테스트 케이스는 20개 이하이며, 전체 수행 시간은 1초 이내. (Java 2초 이내) 

메모리 제한

heap, global, static (총계) : 256MB
stack : 1MB

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 케이스의 개수를 나타내는 자연수 T 가 주어지고,
이후 차례로 T 개의 테스트 케이스가 주어진다. ( 1≤T≤20 )
각각의 테스트 케이스 첫 번째 줄에는 석환이가 말한 숫자 N ( N  은 3,000,000 이하의 자연수)이 주어진다.
테스트 케이스의 둘째 줄에는 N개의 숫자들이 공백(빈칸)을 사이에 두고 주어진다.
각 숫자는 32bit 정수형 변수에 담을 수 있는 음이 아닌 정수이다.

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는  “Case #T”를 출력하여야 한다. 이때 T는 케이스의 번호이다.
그 다음 줄에는 주어진 숫자들 중에서 '홀수' 번만 나타나는 숫자들을 모두 XOR 한 결과를 출력한다.

풀이

우선, 알고리즘 문제풀이에서 1초안에 문제를 풀려면 약 1억번 이하의 연산으로 끝내야 한다. 현재 최대 입력의 크기가 3,000,000 (3백만) 이므로 O(nlogn) 이하의 복잡도로 풀어야 한다.

입력을 모두 배열에 저장하면 O(n) 의 복잡도를 가진다. 그 후, 배열에 저장된 각 숫자가 몇번 등장했는지 세려면, 어떤 숫자인지 모르므로 , n개의 숫자들에 대해 1 ~ 2^31 -1 과 비교해야 한다. 이는 이미 O(n^2)을 초월한다. 즉, 입력을 받는 동시에 숫자의 갯수를 세야 한다. 즉, 미리 각 숫자가 등장한 횟수를 저장하는 배열을 선언해놓고, 입력을 받는 동시에 입력을 인덱스로 가지는 배열의 원소의 값을 증가시킨다면 O(n) 에 등장횟수까지 알아낼 수 있다.

그러나, 여기에는 한가지 문제가 있다. 입력되는 숫자의 범위가 32비트 양의 정수로 너무 크다는 것이다. 그에 반해 입력하는 숫자의 갯수는 최대 3백만개로, 모두 다른 숫자가 입력된다해도 약 0.2% 정도의 공간만 사용한다. 이는 이게 메모리제한에 걸리지 않더라도 너무 큰 낭비다.

이를 해결하기 위해 자바의 Map<K,V>를 사용하기로 했다. Map의 키로 입력받은 숫자를 주고, 값으로 횟수를 가지게 하면, 등장한 숫자의 개수만큼만 공간을 사용하여 등장횟수를 카운트 할 수 있다. 

 

코드

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


class Solution {
	static int Answer;

	public static void main(String args[]) throws Exception	{
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for(int test_case = 0; test_case < T; test_case++) {
			int n = sc.nextInt();
			int array[] = new int[n];
			for(int i=0;i<n;i++) {
				array[i] = sc.nextInt();
			}
			Map<Integer,Integer> map = new HashMap<Integer, Integer>();
			for(int i=0;i<n;i++) {
				if(map.get(array[i])==null) {
					map.put(array[i], 1);
				}else {
					int count = map.remove(array[i]);
					map.put(array[i], count+1);
				}
			}
			for(int i=0;i<n;i++) {
				if(map.get(array[i])!=null && map.get(array[i])%2==1) {
					map.remove(array[i]);
					Answer = array[i];
					break;
				}
			}
			for(int i=0;i<n;i++) {
				if(map.get(array[i])!=null && map.get(array[i])%2==1) {
					map.remove(array[i]);
					Answer ^= array[i];
				}
			}
			System.out.println("Case #"+(test_case+1));
			System.out.println(Answer);
		}
	}
}