[정렬] 중복 확인

 

 

 

설명

 

 

 

 

 

 

 

풀이

 

이 문제는 HashMap을 사용하면 O(n)으로 풀 수 있지만, 정렬로도 이 문제를 풀 수 있음을 보여주기 위해 정렬을 사용했다.

정렬을 사용하면 O(nlog(n))이 된다.

 

로직은 다음과 같다.

• 정답 문자열을 "U"로 초기화한다.
• 오름차순 정렬을 한다. java.util.Arrays 클래스의 sort 메소드를 이용한다.
• 0번 인덱스부터 (배열 길이의 - 1) 번 인덱스까지 반복문을 돈다.
  • 현재 배열값과 현재 배열값의 다음값이 같다면 중복된 것이므로 "D"를 바로 리턴한다.
• 정답 문자열을 리턴한다.

 

 

 

 

코드

 

package inflearn._6_5;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

    public static String solution(int [] arr) {

        String answer = "U";

        // 1. 오름차순 정렬
        Arrays.sort(arr);

        // 2. 이웃한 수끼리 비교해서 같은 수 있으면 중복
        for(int i = 0; i < arr.length-1; i++) {
            if (arr[i] == arr[i+1]) return "D";
        }

        return answer;

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int [] arr = new int[n];

        for(int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            arr[i] = x;
        }

        bw.write(sb.append(solution(arr)).toString());
        bw.flush();

        bw.close();
        br.close();
    }
}