섹션6. Sort - 5. 중복 확인

📌 문제 설명

현수네 반 학생들이 각자 좋아하는 숫자 하나씩을 적어냈습니다. 이 숫자들 중 중복된 숫자가 있는지 확인하는 프로그램을 작성하세요.

---

📝 입력 & 출력

입력

• 첫 줄에 자연수 N (5 ≤ N ≤ 100,000)
• 두 번째 줄에 N개의 자연수 (각각 1 이상 10,000,000 이하)

출력

• 중복이 있으면 "D" 출력
• 모두 다르면 "U" 출력

---

🔹 예제 입력 & 출력

예제 입력 1

8
20 25 52 30 39 33 43 33

 

예제 출력 1

D

---

💡 해결 방법

방법 1: 정렬 후 인접 비교 (강사님 소개 방법)

• 배열을 정렬한 후, 앞뒤 숫자가 같은지 비교
• 중복이 있으면 "D" 반환, 아니면 "U" 반환
• 시간 복잡도: O(N log N)

방법 2: 해시맵 사용 (강사님 추천 방법)

• 숫자를 하나씩 순회하며 HashMap에 저장
• 이미 있는 숫자가 있으면 중복이므로 바로 "D" 반환
• 끝까지 없다면 "U" 반환
• 시간 복잡도: O(N)

---

💻 코드 구현 (Java)

package partSort;

import java.util.*;

public class Problem5 {
	public char solution(int n, int[] arr){
		char answer='U';
		Arrays.sort(arr);
		for(int i=0; i<n-1; i++) {
			if(arr[i]==arr[i+1]) return 'D';
		}
		return answer;
	}

	// public char solution(int n, int[] arr){
	// 	char answer='U';
	// 	HashMap<Integer, Integer> map = new HashMap<>();
	// 	for(int i=0; i<n; i++) {
	// 		if(map.getOrDefault(arr[i], 0)!=0) return 'D';
	// 		map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
	// 	}
	// 	return answer;
	// }

	public static void main(String[] args) {
		Problem5 T = new Problem5();
		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.print(T.solution(n, arr));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 정렬 & 인접 비교 방식

Arrays.sort(arr);
for(int i=0; i<n-1; i++) {
	if(arr[i]==arr[i+1]) return 'D';
}

• 배열을 오름차순으로 정렬
• 인접한 요소만 비교해 중복 여부 확인

2️⃣ 해시맵 방식 (주석 처리된 방법)

HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0; i<n; i++) {
    if(map.getOrDefault(arr[i], 0)!=0) return 'D';
    map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
}

• 중복 발견 즉시 탈출
• 입력 크기가 클 경우 훨씬 효율적

---

⏳ 시간 복잡도 분석

• 방법 1 (정렬): O(N log N)
• 방법 2 (해시맵): O(N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

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