Q. 배열 값 중에서 짝이 없는 홀수 값을 찾으세요.
A = {9, 3, 9, 3, 9, 7, 9}
A. 7
[멍청이 버전]
보기에도 복잡하고 해석하기도 어렵고 무식하게 만들었다.
그래도 꼴에 나머지를 이용하는 기지를 발휘했다.
2로 나눠서 0이 아니면 짝수니까....
(원래 더 똥멍청이 버전이 있는데 그건 너무 부끄러워서 못 올리겠다.)
public int solution(int[] A){
int rtnVal = 0;
Map<Integer, Integer> chkMap = new HashMap<Integer, Integer>();
for(int i = 0 ; i < A.length ; i++){
if(chkMap.get(A[i]) == null){
chkMap.put(A[i], 1);
}else{
chkMap.put(A[i], chkMap.get(A[i]) + 1);
}
}
for(int key : chkMap.keySet()){
if(chkMap.get(key) % 2 != 0){
rtnVal = key;
break;
}
}
return rtnVal;
}
비트연산을 이용한 똑똑한 버전이다.
- 비트 논리곱(&) : 110 & 101 = 100
- 비트 논리합(|) : 110 & 101 = 111
- 비트 상호 배제(^) : 110 & 101 = 011
- 비트 부정(~) : ~110 = 111.....001
비트연산 중 상호배제의 특징을 이용해서 푼 방식이다.
상호배제는 같은 값을 곱하면 0이 되는 것을 이용해서
전체 배열 값을 상호배제 비트연산을 해서 남는 게 홀수라는 거다.
(어떤 값에 ^를 두번하면 원래 값으로 돌아 온다. 간단한 암호에 이용하기도 한다고 함)
public int solution(int[] A){
int rtnVal;
for(int i : A){
rtnVal ^= i;
}
return rtnVal;
}
댓글