[정렬] 중복 확인 .java

설명

현수네 반에는 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

예시 출력 1

D

 

내 풀이 

1. Set의 contains 메서드

중복을 검사하는 문제 => Set

하나씩 차례로 검사하면서 set에 없는 숫자면 넣고, 이미 있는 숫자라면 for문을 빠져나와 답을 출력

 

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];
        Set<Integer> set = new HashSet<>();
        char answer = 'U';
        for(int i = 0; i < n; i++) {
            int cnt = sc.nextInt();
            if(!set.contains(cnt)) {
                set.add(cnt);
            } else {
                answer = 'D';
                break;
            }
        }
        System.out.println(answer);





    }
}

 

2. 배열

• 입력 받은 점수 배열을 오름차순 정렬
• 현재 인덱스와 바로 전 인덱스의 값을 비교하여 같으면 for문을 바로 빠져나온다

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

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];
        char answer = 'U';
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        for(int i = 1; i < n; i++) {
            if(arr[i] == arr[i-1]) {
                answer = 'D';
                break;
            }
        }
        System.out.println(answer);





    }
}

 

 

다른 풀이

해쉬맵이 아닌 정렬로 푼 알고리즘  => O(nlogn)의 시간복잡도

내 배열 풀이를 함수형으로 구현한 코드이다

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


public class Main {
	public String solution(int n, int[] arr) {
		String answer = "U";
		Arrays.sort(arr);//오름차순 정렬
		for(int i = 0; i < n-1; i++) {
			if(arr[i] == arr[i+1] ) return "D";
		}
		
		return answer;
	}

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

💡💡

점점 많은 내용을 배우면서 하나의 방법으로만 구현하는 것이 아닌 여러 방법의 아이디어가 떠오른다