LeetCode: Single Number

오늘 이상하게 코딜리티 문제가 안 들어가져서 오랜만에 LeetCode를 풀었다.
LeetCode에 30일 챌린지가 있어서 시작해보려한다!
일단 오늘이 화요일이니 오늘은 두 문제 풀어야함...
LeetCode의 좋은 점은 Follow up이라고 이런거도 추가해서 다시 풀어보면 어떻니? 라고 물어보는데 이게 참... 생각보다 재밌었다.

문제 풀이

주어진 문제는 어렵지 않았는데 Follow up이 2가지 였는데 하나에 대해서 많이 생각하게되었다.

우선 첫 번째 풀이는 추가 메모리를 사용하지 않고 풀기 위해

• 주어진 배열을 내부정렬
• 2개씩 짝이되는지 확인

하는 방식으로 풀었다.

import java.util.*;
class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for(int index = 0; index < nums.length; index = index + 2) {
            if(index == nums.length - 1) {
                break;
            }
            if(nums[index] != nums[index + 1]) {
                return nums[index];
            }
        }
        return nums[nums.length - 1];
    }
}

리니어하게 풀 수 있는 방법도 해보라고 하는데 도저히 생각이 안나서 솔루션을 확인했다.
솔루션에는 여러 방식을 소개했는데 나머지는 다 알고 있었고, 생각했던 부분들이라서 넘어갔고, 마지막 방식이 굉장히 흥미로웠다.

비트 마스크를 이용하는 방법이었는데 비트 마스크를 이용하면 쉽게 풀리는 문제들이 많긴한데 좀 까다롭다해야하나? 뭔가 풀이법을 떠올리기엔 항상 힘들었던거 같다.

이번 기회에 비트 마스크를 다시 공부하는 계기가 되어야지...
(포스팅했다!)

import java.util.*;
class Solution {
    public int singleNumber(int[] nums) {
        int a = 0;
        for(int i : nums) {
            a ^= i;
        }
        return a;
    }
}