[NeetCode-LeetCode] Single Number JAVA

반응형

728x90

[NeetCode-LeetCode] Single Number - Easy

---

접근

• Map
• XOR

---

풀이

배열의 원소중 중복이 없는 원소를 찾는 문제이다. 배열의 원소들은 모두 2개씩 존재하나 단 한 개의 원소만 2개가 아닌 1개만 존재한다. 문제를 푸는 것 자체는 쉽기 때문에 여러 가지 방법으로 풀 수 있다. 

    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }

        for (Integer i : map.keySet()) {
            if (map.get(i) == 1) {
                return i;
            }
        }
        
        return 0;
    }

처음엔 Map에 매핑을 해 1번만 나온 원소를 결과로 반환하게 풀었다. 시간 복잡도 자체는 O(n)이지만 기본적인 배열의 길이만큼 반복 한 번과 최대 배열의 길이 / 2 만큼의 map 반복을 한번 더 수행하고 map을 사용하며 생기는 오버헤드로 인해 성능에서 많이 밀리게 되었다.

map

---

다음 방법으로 배열을 정렬한 뒤 현재 원소와 다음 원소가 같은지 확인하는 방법이었다. 

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

배열을 정렬해 준 뒤에 처음부터 순회하며 현재 원소와 다음 원소가 같다면 2개가 존재하는 원소로 인덱스를 +2 증가시켜 다음 원소에 접근하게 한다. 만약 현재 원소와 다음 원소가 같지 않다면 해당 원소는 1개만 존재하는 원소로 결과로 반환해 주게 된다. 이 방법 또한 정렬을 수행하는 데 n 그리고 인덱스를 2씩 증가시켜 탐색하므로 최대 n / 2의 연산이 필요하지만 map을 사용하지 않고 배열의 값 자체를 바로 비교하기 때문에 map 사용 오버헤드가 없어 조금 더 빠르게 해결이 가능했다. 

배열

---

XOR

이 문제가 존재하는 이유인 방법이다. 배타적 논리합으로 XOR 연산을 수행하여 두 원소가 같다면 0이 되어 결과로 한 개만 존재하는 원소의 값이 된다는 방법이다. 재귀를 통한 방법으로 수행되며 0과의 XOR 연산은 해당 숫자가 그대로 나온다는 점과 XOR 연산은 교환 법칙, 결합 법칙이 만족한다는 사실을 통해 가능한 방법이다.

    public int singleNumber(int[] nums) {
         return check( 0 , nums);

    }

    public static int check( int k , int[] nums){
        if (k == nums.length){
            return 0;
        }

        return  nums[k] ^ check(k+1 , nums);
    }

k가 배열의 길이가 되면 0을 반환하여 XOR 연산이 시작된다. XOR 연산은 같은 원소를 만나게 되면 0이 되므로 같은 원소가 존재하지 않는 원소만 해당 값으로 남게 된다는 뜻이다.

Input: nums = [4,1,2,1,2]

4 ^ 1 ^ 2 ^ 1 ^ 2 ^ 0 = 
4 ^ 0 ^ 0 = 
4

이렇게 결과로 중복 원소가 아닌 경우 0과의 XOR만 수행되어 해당 원소가 그대로 결과로 반환되게 된다.  

---

전체 코드

map

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }

        for (Integer i : map.keySet()) {
            if (map.get(i) == 1) {
                return i;
            }
        }
        
        return 0;
    }
}

 

배열

class Solution {
    public int singleNumber(int[] nums) {
        int i = 0;
        Arrays.sort(nums);
        while (i < nums.length - 1){
            if (nums[i] != nums[i+1]){
                break;
            }
            else{
                i += 2;
            }
        }
        return nums[i];
    }
}

 

XOR

class Solution {
    public int singleNumber(int[] nums) {
         return check( 0 , nums);

    }

    public static int check( int k , int[] nums){
        if (k == nums.length){
            return 0;
        }

        return  nums[k] ^ check(k+1 , nums);
    }
}