자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Sorting and Searching(정렬, 이분검색과 결정알고리즘)_중복 확인)

 

 

5. 중복 확인

 

예시 입력 1 

8
20 25 52 30 39 33 43 33

예시 출력 1

D

 

내가 푼 풀이 1 (Time: 790ms Memory: 34MB)

나는 정렬도 HashMap도 안쓰고 그냥 간단하게 풀었다. 시간복잡도가 O(n^2)이다. 

하지만 지금 정렬파트를 보고 있으니 정렬로도 연습을 해야 한다.

import java.util.Scanner;

public class Main {

    public String solution(int n, int[] arr) {
        String answer = "U";
        for (int i = 0; i < n-1 ; i++) {
            int tmp = arr[i];
            for (int j = i+1; j < n ; j++) {
                if (tmp == arr[j]) return "D";
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i <n ; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n,arr));
    }
}

내가 푼 풀이 2 (Time: 787ms Memory: 34MB)

 HashMap쓰면 O(n)으로 끝날 수 있다.

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public String solution(int n, int[] arr) {
        String answer = "U";
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int x : arr) {
            map.put(x, map.getOrDefault(x, 0)+1);
            if (map.get(x) > 1) return "D";
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n, arr));
    }
}

 

강의 풀이 (Time: 889ms Memory: 35MB0)

 

시간 복잡도는 O(n log n)이다. 배열을 오름차순으로 정렬한 후에 중복된 값을 찾는다. Arrays.sort(arr) 메서드를 사용하여 배열을 정렬하면 시간 복잡도가 O(n log n)이다. 그런 다음 for 루프를 사용하여 배열을 한 번 순회하므로 추가적인 시간 복잡도는 O(n)이다.

따라서 전체적인 시간 복잡도는 O(n log n) + O(n) = O(n log n)이 된다.

import java.util.Arrays;
import java.util.Scanner;

public class Answer {

    public String solution(int n, int[] arr){
        String answer = "U";
        // 오름차순 정렬
        Arrays.sort(arr);
        // 맨 마지막까지 돌 필요는 없다
        // 왜냐하면 분기문에서 i+1을 비교해주기 때문이다
        for (int i = 0; i < n-1; i++) {
            if(arr[i] == arr[i+1]) return "D";
        }
        return answer;
    }

    public static void main(String[] args) {
        Answer T = new Answer();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i <n ; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n,arr));
    }
}