.leetcode(136. Single Number)

문제

leetcode.com/problems/single-number/

문제 풀기 전

1. 정렬을 사용해서 2개씩 확인해서 다른것이 있으면 그게 하나만 있는거라고 생각했다.

직접 푼 풀이

소요시간: 22분(11:37 ~ 11:59)

class Solution {
    public int singleNumber(int[] nums) {
        //정렬
        Arrays.sort(nums);

        //n,n+1 다르면 n이 정답
        int answer = 0;
        for (int i=0;;i+=2) {
            if (i == nums.length-1) {
                answer = nums[nums.length-1];
                break;
            }
            if (nums[i] != nums[i+1]) {
                answer = nums[i];
                break;
            }
        }

        return answer;
    }
}

느낀점

1. array는 Arrays.sort가 있는데 Collections.sort를 사용하다가 시간을 많이 허비했다. Arrays.stream(nums).boxed().collect(Collectors.toList())와 같이 List형태만 Collections.sort에서 사용가능해서 실패했다.
2. 2번째로는 int의 비교와 Integer의 비교가 다르는데 간과했다. Integer비교는 == !=같은 형태로는 한계가 있다. 정확한 비교는 equals를 통해서 했어야하는데 그러지 못해서 에러가 나서 정답제출에 지연되었다.
3. 시간복잡도 생각이나 제한값 확인을 또 안했다. 누적되는 알고리즘 접근 설명서를 먼저 읽고 풀어야겠다.
4. Set을 이용했어도 되어겠다.
5. 가장 효율적인건 Bit Manipulation이었다. XOR개념에 대해서 한번 알 필요가 있다. XOR은 같은 수끼리하면 0이 나오고 0과 XOR하면 숫자 그대로가 나온다. 2가지가 딱 이 문제를 푸는데 아주 유용한 키이다. 단순히 모든 숫자를 XOR함으로써 구할 수 있다. XOR은 교환법칙과 결합법칙이 성립하므로 순서에 상관없이 계산이 가능하다고 한다고 한다. 언젠가 XOR에 대해서 한번 더 다룰 기회가 있을거 같다.

솔루션 공부 후 추가로 푼 풀이

# Set을 이용한 풀이
class Solution {
    public int singleNumber(int[] nums) {
       Set<Integer> box = new HashSet<>();

       for (int i=0; i<nums.length; i++) {
           if (box.contains(nums[i])) {
               box.remove(nums[i]);
           } else {
               box.add(nums[i]);
           }
       }

        return box.stream().findFirst().get();
    }
}

# Bit Manipulation을 이용한 풀이
class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int each: nums) {
            ret ^= each;
        }

        return ret;
    }
}

누적되는 알고리즘 접근 설명서

1. 제한값이 있는지 확인한다.

2. 최대 시간복잡도나 최대 경우의 수를 유추해본다.

3. 기본으로 주어지는 메소드에서 해결이 가능한지 생각해본다. > 메소드를 만들어 사용한다. > 전역변수를 과감히 도입한다.

4. recursion(Brute Force, Back Tracking)으로 가능할지 먼저 생각해본다. 이 후에 iterative하게 풀 수 있을지도 생각해본다. iteratvie하게 풀때는 stack을 이용해본다. 경우의 따라 queue를 사용해볼 수 있다.

5. recursion일 경우, 종료조건을 먼저 만들고 로직을 만든다.

6. 주어진 Input데이터를 더렵힐 수도 있다고 생각해본다. 덮어쓰기한다던지, 더해서 합값으로 치환한다던지 말이다.

7. Integer비교가 있다면 equals를 사용하자.