[코딩연습] Single Number 하나뿐인 숫자 찾기

LeetCode 문제 중 난이도 Easy인 Single Number이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

비어있지 않은 정수 배열에서, 하나를 뺀 모든 요소들은 두개씩 들어있다. 하나뿐인 요소를 찾아라.

알고리즘은 선형시간의 복잡도(O(n))를 가져야 한다. 추가적인 메모를 사용하지 않고 가능한가?

가장 먼저 떠오른 알고리즘은 먼저 배열을 정렬 한 뒤, 배열을 처음부터 탐색해 앞이나 뒤 요소와 둘다 같지 않은 요소를 찾는 것이다.예를 들어 [1,1,2,3,3]의 경우 2가 유일한 요소로 앞의 1과도 다르고 뒤의 3과도 다르다. 코드는 다음과 같다.

class Solution {
    public int singleNumber(int[] nums) {

        Arrays.sort(nums);
        
        //배열의 길이가 1이거나, 첫번째요소와 두번째요소가 다르면 첫번째요소가 single one
        if(nums.length==1 || nums[0]!=nums[1]) return nums[0];
        
        //앞과 뒤 요소중 둘다 같은게 없으면 single one이므로 출력
        for(int i = 1; i<nums.length-1 ; i++){
            if(nums[i]!=nums[i-1] && nums[i]!=nums[i+1]) return nums[i];
        }
        
        //배열을 다 돌 때까지 못찾으면 배열의 마지막요소가 single one
        return nums[nums.length-1];
    }
}

이 경우에는 추가적인 메모리 사용은 없지만 Java의 Array.sort 정렬을 하는데 최대 O(nlogn) 시간이 들므로 문제의 요구사항인 선형시간 O(n)을 초과한다. 

두번째 방법은 비트연산자를 이용하는 것이다. 비트연산자를 잘 모를 경우 아래 포스팅을 참고하자.

2019/03/16 - [프로그래밍문제풀기] - 비트연산자란?

비트연산자중 ^(XOR)을 사용할 것이다. XOR연산자는 양쪽 비트가 서로 다른 경우에 1을, 같은 경우에는 0을 반환한다.

A ^ 0 = A

A ^ A = 0

A ^ B ^ A = A ^ A ^ B = 0 ^ B = B

따라서 배열의 모든 요소로 XOR 연산을 하면 두 개씩 있는 요소들은 서로 상쇄되어 사라지고 딱 하나만 있는 요소를 찾을 수 있다.

class Solution {
    public int singleNumber(int[] nums) {

        int singleone=0;
        
        for(int i = 0 ; i<nums.length ; i++){
            singleone=singleone^nums[i];
        }

        return singleone;
    }
}
 

위의 코드에서 singleone이라는 정수형을 하나 추가로 사용했지만 이 경우 nums배열이 아무리 커져도 영향을 주지 않기 때문에 공간복잡도는 O(1)이고 추가적인 메모리는 사용하지 않는다고 봐도 된다.

문제 출처 - https://leetcode.com/problems/single-number