Leetcode[day7] - Counting Elements

Given an integer array arr, count element x such that x + 1 is also in arr.
If there're duplicates in arr, count them seperately.

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

1. 알고리즘을 해결하기 위해서 생각한 방법

 

- 우선, 문제가 이해를 하는게 어려웠다.

- 문제는 배열 안에 x가 있을 때, x+1이 있는 원소를 카운팅 하시오.

- 우선, 해당 문제를 풀기 위해서, Map을 활용했다. Map은 카운팅 하려는 숫자 key, 카운팅 value가 들어있다. 

- 그리고 주어진 배열을 sort 한 후, Map에 카운팅을 해서 값을 넣어준다.

- 그리고, map에 해당 key의 다음 값이 존재 한다면, 현재 해당 값이 모두 성립되기 때문에 answer에 누적해준다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 없었다.

 

3. 내가 작성한 알고리즘

 

class Solution {
    public int countElements(int[] arr) {
        // [1,3,2,3,5,0]
        // [0,1,2,3,3,5]
        // [0,0,0, 1,1,1, 2]
        //Map으로 한다면? 0,3 1,3 2,1
        Map<Integer, Integer> map = new HashMap<>();
        Arrays.sort(arr);//sorted array
        int answer = 0;
        for(int num : arr){
            if(map.containsKey(num)){
                map.put(num, map.get(num)+1);
            }else{
                map.put(num, 1);
            }
        }
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            Integer key = entry.getKey();
            if(map.containsKey(key+1)){
                answer += map.get(key);
            }
        }
        return answer;
    }
}

4. 내가 작성한 알고리즘 결과

 

결과가 없다..

 

5. 다른 사람이 작성한 알고리즘 보기

 

class Solution {
    public int countElements(int[] arr) {
        Set<Integer> lookup = new HashSet<>();
        for(Integer i: arr){
            lookup.add(i);
        }

        int count =0;

        for(Integer i:arr){
            if(lookup.contains(i+1)){
                count++;
            }
        }
        return count;
    }
}

 

6. 다른 사람이 작성한 알고리즘을 보고 배운점

 - HashMap에서 벗어나서, 자유롭게 자료구조를 사용해야 한다.

 - lookup 변수에는 중복을 제거하고, 이미 값을 갖고 있는 배열의 원소들을 추가해준다.

 - 그리고, 다시 주어진 input array를 돌릴 때, lookup.contains() O(1)을 통해서, count를 추가해준다.

 - Map보다 훨씬, 직관적이고, 효율도 좋아보인다.

 

7. 반성할 점

 - 자료구조를 좀 더 생각을 하고 쓰자.

 

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3289/

Explore - LeetCode

다른 사람 문제 참조 : https://stackoverflow.com/questions/61166418/leetcode-counting-elements-with-on-time-complexity

Leetcode : Counting Elements with O(n) time Complexity