코딩연습2
Array에서 중복되지 않는 value 값을 구하는 문제이다.
처음엔 HashMap을 사용해서 이미 key 값을 가지고 있는 경우 value +1 해주고 value 가 1인 entry의 key를 리턴하는 방식으로 풀이했다.
결과는 정확도 66%..ㅠㅠ 흑..
Task Description
A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
For example, in array A such that:
A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9
- the elements at indexes 0 and 2 have value 9,
- the elements at indexes 1 and 3 have value 3,
- the elements at indexes 4 and 6 have value 9,
- the element at index 5 has value 7 and is unpaired.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.
For example, given array A such that:
A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9
the function should return 7, as explained in the example above.
Write an efficient algorithm for the following assumptions:
- N is an odd integer within the range [1..1,000,000];
- each element of array A is an integer within the range [1..1,000,000,000];
- all but one of the values in A occur an even number of times.
class Solution(int[] A){
HashMap<Integer> nums = new HashMap<Integer>();
int result = 0;
for(int i=0;i<A.length;i++){
if(!nums.containKey(A[i]){
nums.put(A[i],1);
}else{
nums.put(A[i],nums.get(A[i])+1);
}
}
Set set = nums.entrySet();
Iterator i = set.iterator();
while(i.hasNext()){
Map.Entry entry = (Map.Entry)i.next();
if((Integer)entry.getValue()==1){
result = (Integer)entry.getKey();
}
}
return result;
}
내가 푼 방식
다른 블로그를 찾아보니 xor 로 한줄만에 풀 수 있었다.
xor 연산자 특징
비교할 두 값을 이진수로 바꾼 후, 한 자리씩 비교하여 같으면 0, 다르면 1을 리턴한다.
xor 연산의 특징은 중복되는 수는 저절로 없애준다는 것이다.
3^3 = 0011^0011 = 0000 = 0
3^3^5 = 0011^0011^0101= 0101 = 5
1^3^1^3^5 = 0001^0011^0001^0011^0101 = 5
이것처럼 자동으로 1개만 남는 수를 리턴할 수 있다.
위의 문제에 xor연산을 적용하면 아래와 같이 단순화시킬 수 있다.
class Solution(int[] A){
int result = 0;
for(int a : A){
result ^= a;
}
return result;
}
넘나 간단한 것.. xor 연산 완전히 이해했다. 다음에 비슷한 문제가 나온다면 적용할 수 있을 것 같다.
2번째 문제 풀이 완료!
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[java] 백준 1012번 : 유기농 배추 (bfs, dfs) (0) | 2021.02.19 |
---|---|
[codility] Binary Gap 구하기 (0) | 2019.09.03 |
[카카오 데모테스트] 직사각형의 좌표 구하기 (0) | 2019.08.26 |