[인프런] 중복 확인

난이도

• Easy

문제 설명

현수네 반에는 N명의 학생들이 있습니다.
선생님은 반 학생들에게 1부터 10,000,000까지의 자연수 중에서 각자가 좋아하는 숫자 하나 적어 내라고 했습니다.
만약 N명의 학생들이 적어낸 숫자 중 중복된 숫자가 존재하면 D(duplication)를 출력하고,
N명이 모두 각자 다른 숫자를 적어냈다면 U(unique)를 출력하는 프로그램을 작성하세요.

입력 형식

• 첫 번째 줄에 자연수 N(5<=N<=100,000)이 주어진다.
• 두 번째 줄에 학생들이 적어 낸 N개의 자연수가 입력된다.

출력 형식

• “D” 혹은 “U”

예제 입력 및 출력

**예제 1:**
입력: 
8
20 25 52 30 39 33 43 33
출력: "D"

접근 방법

• 값을 독립적으로 세기 위해 set에 담는다
• 최초 기입한 횟수와 set에 담긴 길이와 비교하고, 적으면 중복값이 사라진 것임으로 “D” 아니면 “U”이다

시간 및 공간 복잡도

• 시간 복잡도 : O(NlogN) : 입력 받은 원소들을 HashSet에 저장: O(N) + O(M)
• 공간 복잡도 : O(N) : 집합에 저장

코드 구현

import java.util.*;

public class App {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Integer> set1 = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set1.add(sc.nextInt());
        }

        if (set1.size() < n) {
            System.out.println("D");
        } else {
            System.out.println("U");
        }

        sc.close();
    }
}