[JAVA | Leetcode] 163. Single Number

연어·2024년 12월 18일
0

코딩테스트 문제를 풀어보다가 새로운 자극을 얻게 된 문제가 있어 오랜만에 코딩테스트 글을 정리해본다.

문제

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.

비어 있지 않은 정수 nums 배열이 주어지면, 모든 요소가 하나를 제외하고 두 번 나타납니다. 그 하나를 찾으세요. 선형 런타임 복잡도를 가진 솔루션을 구현하고 상수 추가 공간만 사용해야 합니다.

✅ 선형 런타임 복잡도
알고리즘의 실행 시간이 입력 데이터 크기(n)에 비례해 증가하는 것으로, 입력 데이터의 크기가 커질수록 실행 시간도 그만큼 증가한다.
빅오 표기법 - O(n)O(n)

예시

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

제약사항

  • 1 <= nums.length <= 3 * 10⁴
  • 3 * 10⁴ <= nums[i] <= 3 * 10⁴
  • Each element in the array appears twice except for one element which appears only once.
    • 한 번만 나타나는 한 요소를 제외하고 배열의 각 요소는 두 번 나타납니다.

작성한 코드

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1) return nums[0];

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        for (int key : map.keySet()) {
            if(map.get(key) == 1) return key;
        }

        return nums[0];
    }
}

문제를 읽고 먼저 단순하게 생각나는 대로 풀어본 코드이다.

제약사항이 nums.length 가 최대 3 * 10⁴ 이어서 O(n²)O(n²)(= 10⁸) 가 넘지 않도록 한 번의 nums 반복을 돌렸다.

  • numsnummap 에 최대 2의 value 가 존재할 것이다.
  • map 을 반복하면서 value 가 1 인 key 를 반환한다.

nums 에는 한 숫자당 최대 2번 들어가 있기 때문에 map에는 최소 nums.length / 2 만큼의 key 를 갖고 있을 것이다. nums.length 가 여러번 반복하는 최악의 상황은 면하지만 map 자체로도 상당히 많은 key를 가지고 있기 때문에 두 번의 반복문이 상당히 비효율적으로 느껴졌다.

Submit 해 봤더니 13ms 가 측정됐다. 🫨

13ms 는 그냥 넘어갈 수 없다 … 하지만 마땅한 다른 풀이가 떠오르지 않는다.
최소 실행시간으로 측정된 다른 사람들의 코드를 참고했다.

참고한 코드

class Solution {
    public int singleNumber(int[] nums) {
        int result=0;
        for(int num:nums){
            result ^=num;
        }
        return result;
    }
}

나는 사용한 적이 극히 드물었던 ^= 계산식을 사용했다.

한 숫자 당 2번의 중복이 있는 배열 내에서 중복이 없는 숫자를 거르기 위한 방법으로 해당 계산식을 도출해 낼 수 있다는 게 대단하다고 느껴지면서 아직 나는 좀 더 생각의 범위를 넓혀야되겠다는 생각이 들었다.

^= 는 XOR 연산으로, 아래와 같은 특징을 가진다.

  • a ^ a = 0 : 동일한 숫자를 XOR하면 결과는 0이다.
  • a ^ 0 = a : 어떤 숫자와 0을 XOR하면 결과는 원래 숫자이다.
  • (a ^ b) ^ c = a ^ (b ^ c) : 순서에 관계 없이 교환과 결합이 자유롭다.

nums = {4, 1, 2, 1, 2} 일 경우 처리 순서는 아래와 같다.

  • result = 0
  • result ^= 40 ^ 4 = 4
  • result ^= 14 ^ 1 = 5 (0100 ^ 0001 = 0101)
  • result ^= 25 ^ 2 = 7 (0101 ^ 0010 = 0111)
  • result ^= 17 ^ 1 = 6 (0111 ^ 0001 = 0110)
  • result ^= 26 ^ 2 = 4 (0110 ^ 0010 = 0100)

4 ^ 1 ^ 2 ^ 1 ^ 2 는 교환법칙 및 결합법칙에 따라 1 ^ 1 ^ 2 ^ 2 ^ 4 로 보면 더 이해가 간다.

(1 ^ 1) = 0, (2 ^ 2) = 0 이기 때문에(같은 숫자의 XOR 연산 결과는 0이기 때문에) 두 번 중복해서 XOR 연산되는 숫자는 0으로 상쇄되고 중복되지 않는 숫자만 남게 되는 것이다.

생각의 확장이 필요하다고 느끼게 해준 문제와 풀이였다.

문제 출처

https://leetcode.com/problems/single-number/description/

profile
끄적이는 개발자

0개의 댓글