설명

현수네 반에는 N명의 학생들이 있습니다.

선생님은 반 학생들에게 1부터 10,000,000까지의 자연수 중에서 각자가 좋아하는 숫자 하나 적어 내라고 했습니다.

만약 N명의 학생들이 적어낸 숫자 중 중복된 숫자가 존재하면 D(duplication)를 출력하고,

N명이 모두 각자 다른 숫자를 적어냈다면 U(unique)를 출력하는 프로그램을 작성하세요.

코드

public class DuplicationCheck {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int[] arr = new int[input1];
        for(int i=0; i<input1; i++){
            arr[i] = in.nextInt();
        }
        String solution = solution2(arr);
        System.out.println(solution);
    }
    public static String solution(int[] arr){
        int length = arr.length;
        for(int i=0; i<length; i++){
            for(int j=i+1; j<length; j++){
                if(arr[i] == arr[j]) return "D";
            }
        }
        return "U";
    }
    public static String solution2(int[] arr){
        Arrays.sort(arr);
        for(int i=0; i<arr.length-1; i++){
            if(arr[i] == arr[i+1]) return "D";
        }
        return "U";
    }
}

이번 문제는 시간 복잡도가 O(N^2) 이하로 풀어야하는 중복 검사 문제다. 내가 풀이한 방법은 2중 for문이지만 두번째 for문이 i가 커질수록 j의 반복 횟수가 줄어들기 때문에 풀이를 통과한 것 같다. 그리고 강의에서 나온 풀이 방법은 sort 후 다시 for문으로 검사하기 때문에 NlogN의 복잡도가 나온다. 정렬, 탐색 카테고리의 문제라 탐색일줄 알고 풀었는데 정렬 문제였다...ㅎ

그리고 강사님께서 이 방법보다 해쉬를 사용하면 O(N)으로 풀 수 있다고 하셨다. Hash를 사용하는 방법과 Set을 이용하여 문제를 풀이할 방법을 바로 떠올렸다면 굳이 풀어볼 필요는 없고 다음에 이런 문제에서 사용해도 좋을 것 같다!

정렬로 중복검사 문제 풀이 하지만 Hash나 Set을 사용하는게 더 쉽고 빠름!