.leetcode(1346. Check If N and Its Double Exist)

https://leetcode.com/problems/check-if-n-and-its-double-exist/

 

1. 2022.04.23 시도

소요시간: 6분

class Solution {
    public boolean checkIfExist(int[] arr) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        
        Set<Integer> numbers = new HashSet<>();
        Set<Integer> doubledSet = new HashSet<>();
        for (int each: arr) {
            if (numbers.contains(each)) {
                if (each == 0) {
                    return true;
                }

                continue;
            }

            if (doubledSet.contains(each) || doubledSet.contains(each*2)) {
                return true;
            }
            
            numbers.add(each);
            doubledSet.add(each*2);
            doubledSet.add(each);
        }
        
        return false;
    }
}

풀이 접근 과정

가장 먼저 arr의 edges케이스인 null체크와 길이 체크를 한다.

doubled된 숫자와 double이 될 수 있는 가능성이 있는 숫자를 doubledSet에 넣는다.
ex) 14라는 숫자는 28로도 저장하고, 14로도 저장

위에 처럼 저장하면 같은 숫자가 나올 때 예외처리가 필요하여, 실제로 이미 doubled에 들어간 숫자들은 numbers라는 셋으로 관리한다.

다만 numbers중에 0 또한 edge케이스이기 때문에 예외처리한다.

시간복잡도는 O(n), 공간복잡도 O(n)으로 풀이된다.

 

느낀점

• 간단한 문제이지만 솔직히 Edge케이스를 생각 못했다. edge케이스를 생각하는 버릇을 들여야겠다.
• 다른 사람들 풀이를 보니 더욱 간단하게 풀 수 있다.

class Solution {
    public boolean checkIfExist(int[] arr) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        
        Set<Integer> doubledSet = new HashSet<>();
        for (int each: arr) {
            if (doubledSet.contains(each*2) || ((each % 2 == 0) && doubledSet.contains(each/2))) {
                return true;
            }
            
            doubledSet.add(each);
        }
        
        return false;
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형