[인프런 알고리즘] Chapter 6, 5번 문제(중복 확인)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class sec06_05 {
    public static char solution(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        for (int i : arr) set.add(i);
        return (arr.length == set.size()) ? 'U' : 'D';
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; ++i) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(arr));
    }
}

 

설명

• 배열 arr에 있는 모든 값을 HashSet에 추가한다.
• 만약 배열 arr의 길이와 HashSet의 크기가 같으면 중복이 없다는 뜻이므로 ‘U’를 반환한다.
• 배열의 길이와 HashSet의 크기가 다르면 중복이 있다는 뜻이므로 ‘D’를 반환한다.
• HashSet에 값을 추가하는 연산은 평균적으로 O(1)이므로 배열의 크기가 N일 때 전체 시간 복잡도는 O(N)이다. 이는 매우 효율적이다.