[LeetCode] Java - Single Number

 

LeetCode에서 30일 챌린지가 있어 4월 1일부터 도전하기로 했습니다.

하나하나 풀어보죠

 

1일차 문제는 Single Number 입니다.

 

Solution을 보지 않고 문제를 해결하기 위해 생각해보았습니다.

 

문제는 중복되는 수가 아닌 1개만 존재하는 수를 찾는 문제입니다.

저는 처음에 sort 후 앞 뒤로 동일한 숫자가 없다면 중복되지 않다고 생각하여 출력했습니다.

 

public static int singleNumber(int[] nums) {
 
    Arrays.sort(nums);
    if(nums.length == 1) return nums[0];        
    if(nums[0] != nums[1]) return nums[0];
    if(nums[nums.length-1] != nums[nums.length-2]) {
        return nums[nums.length-1];
    }
    for(int i=1; i<nums.length-1; i++) {
        if(nums[i] != nums[i+1] && nums[i] != nums[i-1]) {
            return nums[i];
        }
    }       
    return 0;
}

이 정도면 괜찮겠지 생각하고 제출해보니 3ms.. 흠 평균안에도 못들었습니다.

 

흑 안돼 더 줄여봐야해 하고 생각하고 풀어봤는데 도저히 생각이 나지않더라구요.

그래서 Solution을 보고 공부해보니 XOR을 활용하면 더 빠르게 문제 해결이 가능했습니다.

 

2진수 연산 방법이 역시 가장 빠르더군요

 

public static int singleNumber(int[] nums) {
 
    if(nums == null || nums.length == 0) return 0;

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

    return ans;
    
}

XOR로 변경해 제출하니 0ms가 나옵니다.

 

XOR 계산법 오늘도 공부하면서 하나 배워갑니다.