Codility - Odd Occurrences In Array 풀이 (Java8)

Codility - Odd Occurrences In Array  풀이

문제

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

OddOccurrencesInArray coding task - Learn to Code - Codility

 

문제요약

---

• [1..1,000,000] 범위 숫자 중 Random 홀수 N이 있다
• 배열 A는 길이가 N 이다
• 배열안, 숫자는 1이상 10억 이하의 숫자를 가진다
• 배열 A의 숫자들은 pair를 가지는데 같은 숫자면 pair이다
• pair 가 아닌 odd 인 숫자를 찾아서 출력하라 (반드시 1개)

 

접근방법

---

• 배열 A의 number 들은 최대 10억이므로 counting 배열을 만들 수 없다.
• 1안, 정렬을 한다면 merge sort들을 활용하여 O(nlogn) 으로 정렬 후 odd를 찾으면 된다.
• 2안, Set 종류의 자료구조를 사용하는 방법도 있다. 
• 3안, ex-or 활용하여 '9 ^= 9' 의 결과가 0 인것을 활용한다.

풀이

---

public class OddOccurrencesInArray {

	public static void main(String[] args) {
 
		int[] A = {9,3,9,3,9,7,9};
		
		System.out.println(solution(A)); 
		
	}
		
	public static int solution(int[] A) {
        
		int result = 0;
		
		for (int i : A) {
			result ^= i;
		}
		
		return result;
    }

}

 

여담이지만 ^= 를 활용하면 이런것도 된다.

 

a ^= b;

b ^= a;

a ^= b; 

 

이렇게 3번 수행하면 a, b 값이 서로 변경된다.