본문 바로가기
TechNical/JAVA

[codility] OddOccurrencsInArray

by 강멍멍이 2018. 1. 12.
반응형

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;

}

반응형

댓글