배열에서 홀수 번 등장하는 숫자를 찾는 Java 프로그램

개요

정수 배열에 여러 숫자가 섞여 있을 때, 대부분의 요소는 짝수 번 반복되지만 단 하나의 요소만 홀수 번 나타나는 경우가 있습니다. 이런 상황에서 해당 요소를 찾아내는 것은 코딩 테스트나 실무에서 자주 마주치는 문제입니다. 이 글에서는 Java로 이 문제를 해결하는 방법을 단계별로 살펴보겠습니다.

배열에서 홀수 번 등장하는 숫자를 찾기 위한 Java 코드는 다음과 같습니다.

예제 코드

public class Demo {
    static int odd_occurs(int my_arr[], int arr_size){
        int i;
        for (i = 0; i < arr_size; i++){
            int count = 0;
            for (int j = 0; j < arr_size; j++){
                if (my_arr[i] == my_arr[j])
                    count++;
            }
            if (count % 2 != 0)
                return my_arr[i];
        }
        return -1;
    }
    public static void main(String[] args){
        int my_arr[] = new int[]{ 34, 56, 99, 34, 55, 99, 90, 11, 12, 11, 11, 34 };
        int arr_size = my_arr.length;
        System.out.println("배열에서 홀수 번 발생하는 숫자는 ");
        System.out.println(odd_occurs(my_arr, arr_size));
    }
}

실행 결과

배열에서 홀수 번 발생하는 숫자는
34

코드 설명

Demo라는 이름의 클래스에는 정적(static) 메서드인 odd_occurs가 정의되어 있습니다. 이 메서드는 정수 배열을 처음부터 끝까지 순회하면서 각 요소가 배열 전체에서 몇 번 등장하는지 세어 봅니다. 그리고 등장 횟수가 홀수인 첫 번째 요소를 발견하면 즉시 해당 값을 반환합니다. 만약 조건에 맞는 요소가 없다면 -1을 반환하여 결과가 없음을 알립니다.

main 메서드에서는 정수 배열을 하나 선언하고, 배열의 길이를 변수에 저장합니다. 이후 배열과 길이를 인자로 전달하여 odd_occurs 메서드를 호출하고, 결과와 함께 안내 메시지를 콘솔에 출력합니다. 위 예제에서는 34가 세 번 등장하므로 34가 출력됩니다.

성능 개선 팁

위 방식은 중첩 반복문을 사용하기 때문에 시간 복잡도가 O(n²)입니다. 배열의 크기가 커지면 실행 속도가 느려질 수 있습니다. 이 경우 모든 요소를 XOR(배타적 OR) 연산으로 누적하는 방법을 활용하면 시간 복잡도를 O(n)까지 줄일 수 있습니다. 같은 숫자끼리 XOR하면 0이 되고, 홀수 번 등장한 숫자만 최종적으로 남는다는 원리를 이용합니다. 단, 이 방식은 홀수 번 등장하는 요소가 정확히 하나일 때 유효합니다.