[코딜리티/Codility] OddOccurrencesInArray 문제

---

---

# 문제

간단하게 말하면 중복값을 제거한 후 나머지 유니크한 값을 리턴해주는 함수를 만드는 것이다.

예를 들어

  A[0] = 9  A[1] = 3  A[2] = 9

  A[3] = 3  A[4] = 9  A[5] = 7

  A[6] = 9

위와 같은 배열이 들어오면

인덱스 0, 2가 9의 값으로 중복이므로 삭제

인덱스 1, 3가 3의 값으로 중복이므로 삭제

인덱스 4, 6가 9의 값으로 중복이므로 삭제

나머지 7의 값이 유니크 값이므로 7을 리턴해 줌

이런식으로 소스코드를 구현해 주면 된다.

# 초기 소스코드

class Solution {
    public int solution(int[] A) {
        int index = 0;
        String ValueTxt = "";        // 배열의 값을 저장하는 변수
        String Separator = ";;";    // 문자열 구분자
 
        for(int i = 0; i < A.length; i++){
            if(ValueTxt.indexOf(Integer.toString(A[i]) + Separator) >= 0){
                // 값이 존재하는 경우 문자열에서 값 삭제
                ValueTxt = ValueTxt.replace(Integer.toString(A[i]) + Separator, "");
            }else{
                // 값이 존재하지 않는경우 구분자와 함께 값 추가
                ValueTxt += Integer.toString(A[i]) + Separator;
            }
        }
 
        // 구분자 삭제후 정수로 변경
        return Integer.parseInt(ValueTxt.replace(Separator, ""));
    }
}

처음 문제를 받고 풀 때 소스코드다.

하지만 이렇게 풀게 되면 시간복잡도에서 문제가 생기고

배열이 string 할당 공간보다 넘어가는 경우 오류가 발생한다.

그래서 좀더 최적화된 소스코드를 찾아보니 아래와 같은 코드를 발견했다.

# 최적 소스 코드

class Solution {
    public int solution(int[] A) {
        int result = 0;
 
        for(int i = 0; i < A.length; i++){
            // XOR 비트 연산자로 중복값 삭제
            result = result ^ A[i];
        }
        
        return result;
    }
}

<출처 : http://hojak99.tistory.com/314>

나는 위 소스를 보고 놀라움을 느꼈다.

학부 시절 비트연산자를 배울 때 그렇게 중요하다고 못느꼈다.

하지만 이번에 알고리즘을 공부하다 보니

비트연산자의 중요성을 알게 되었다.

# 마무리

위 포스트는 제가 직접 제작한 것 입니다.

그렇기 때문에 틀린점이나 설명이 엉성한 점이 존재할 수 있습니다.

만약 틀린점이나 설명이 엉성한 부분이 존재하면 댓글로 알려주세요.

빠른 처리 하도록 하겠습니다.

티스토리 앱으로는 댓글 이용이 불가능 하므로 웹 브라우저로 봐 주세요

(URL : http://junprogramer.tistory.com/)

읽어주셔서 감사합니다.