Codility Lesson 02 - OddOccurrencesInArray( JAVA )

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

OddOccurrencesInArray coding task - Learn to Code - Codility

문제

- 홀수( odd number )로 이루어진 배열에서 같은 수를 가진 쌍( pair )이 아닌 것을 찾는 문제

- A는 non-empty( 비어 있지않은 ) 배열이다.

- 예시

[ 9, 3, 9, 3, 9, 7, 9 ]

쌍( pair ) : index 0, 2( 9 ), index 1, 3( 3 ), index 4, 6( 9 )

unpair : index 5( 7 )

예시에서 답안 : 7( return value )

- 제한조건

• 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.

N은 홀수 integer로 1 ~ 1,000,000 사이의 수

A의 각 원소들은 1 ~ 1,000,000,000 사이의 수

A 배열의 한개의 값을 제외하고, 짝수개( even number )를 발생( occur )한다.

- 참고사항

Integer의 범위 : -2,147,483,648 ~ 2,147,483,647

 

풀이

- index를 찾는 것이 아닌 값만을 찾는 것이고, 제한조건 3번에 따라서 정렬 후 찾는 방법을 사용할 수 있다.

- 최악의 시간복잡도의 경우 O(N), for문 한번 돌았을 때로 시간조건을 통과할 수 있을 것이다.

- 정렬 후( 기본 오름차순 정렬 ) 같은 값이 반복되면 임시변수( answer )를 0으로 초기화 하는 방법으로 풀이

 

소스코드

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        Arrays.sort(A);
        int answer = 0;
        for( int i:A ){
            if( answer == 0 ){
                answer = i;
            }else{
                if( answer == i ){
                    answer = 0;
                }else{
                    break;
                }
            }
        }

        return answer;
    }
}