[Algorithm] 중복 확인(Stack, HashMap, Array)

설명

1부터 10,000,000까지의 자연수 중에서 아무 숫자 선택한다.

만약 N명의 사람들이 선택한 숫자 중 중복된 숫자가 존재하면 D(duplication)를 출력하라.

N명이 모두 각자 다른 숫자를 적어냈다면 U(unique)를 출력하라.

 

입력

첫 번째 줄에 자연수 N(5<=N<=100,000)이 주어진다.

두 번째 줄에 사람들이 적어 낸 N개의 자연수가 입력된다.

 

출력

첫 번째 줄에 D 또는 U를 출력한다.

 

* 문제는 입력값의 중복을 확인하는 간단한 문제로 3가지 방식으로 가능.

1. Stack

2. HashMap

3. Array

 

입력.

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Solution(n, arr);
    }

 

 

풀이.

1. Stack의 contains 활용

: contains 메서드를 활용하여 Stack에 값이 존재하는지 확인한다.

    static void Solution(int n, int[] arr){
        String result = "U";
        Stack<Integer> stack = new Stack<>();
        for(int x : arr){
            if(stack.contains(x)) {
                result="D";
                break;
            }else{
                stack.push(x);
            }
        }
        System.out.println(result);
    }

2. HashMap의 key, value 활용

: 값을 Hash의 key로 담고 value에 카운트를 1씩 더해준다.

: getOrDefault로 해당 key의 value를 가져오되 없을 경우 디폴트값으로 0을 주고 마지막으로 그리고 +1 해준다.

: 중복값이 들어올 경우 해당 key의 value < 1으로 중복이 된다.

    static void Solution(int n, int[] arr){
        String result = "U";
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int x : arr){
            map.put(x,map.getOrDefault(x,0)+1);
            if(map.get(x) > 1) result = "D";
        }
        System.out.println(result);
    }

3. Arrays의 sort 활용

: 배열을 오름차순으로 미리 정렬후 배열의 인접인덱스 끼리 비교한다.

    static void Solution(int n, int[] arr){
        String result = "U";
        Arrays.sort(arr);
        for (int i = 0; i < n-1; i++) {
            if(arr[i] == arr[i+1]) {
                result = "D";
                break;
            }
        }
        System.out.println(result);
    }

 

---

 

정리 :

3번(배열)은 sort로 인하여 시간 복잡도가 O(NlogN)이므로 기존 1, 2번의 O(N)보다 비효율적이다.