[Java] 배열 중복 제거

1. 문제 설명

배열의 값을 입력받아 중복을 제거하는 알고리즘 구현
ex) [1, 2, 3, 3, 3, 4, 4, 5] = [1, 2, 3, 4, 5]

입력 형식

첫 줄에 데이터의 수 N이 1이상 10만 이하의 자연수로 공백없이 주어진다.

출력 형식

응모한 모든 시리얼 번호 중 두 번이상 응모한 번호를 제외하고, 나머지 번호들을 공백으로 구분하여 한 줄에 오름차순으로 출력한다.

2. 알고리즘 접근

문제 유형 파악

1. 중복인 데이터를 찾아 중복을 삭제해야 하기에 이는 탐색 문제
2. 중복을 제거 한 후 원소를 오름차 순 하면 된다
3. 중복 제거 후 데이터 개수를 예측하기 어렵다 => 가변 길이 배열(ArrayList) 이용

문제 해결 방법

1. 빈도수 배열을 활용한 방법

중복이 없다 == 빈도수가 1

n = 6 // 데이터 수
data = [2, 3, 3, 4, 7, 5] // 실제 입력 데이터
table = [0, 0, 1, 2, 1, 1, 0, 1] // 빈도수 데이터

위와 같이 빈도수 데이터에서 1인값들만 출력하면 정답을 도출할 수 있다

2. 데이터를 정렬하여 정렬된 데이터의 성질을 활용한 방법

데이터를 정렬했다 = 같은 데이터가 인접해있다
-> 정렬 된 배열에서, 양쪽의 인접한 원소들과 다른값이라면 중복이 아니다
i = 0일땐 왼쪽값을 검사하지않고
i = n-1일땐 오른쪽값을 검사하지 않는다
이 방법을 이용해 풀어보자

3. 알고리즘 풀이

1. 빈도수 배열을 활용한 풀이

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Q3C {
    public static final Scanner sc = new Scanner(System.in);
    public static final int MAX_N = 100000;
    private static ArrayList<Integer> getUniqueElements(int[] data, int n) {
        ArrayList<Integer> ret = new ArrayList<>();
        int[] table = new int[MAX_N + 1];

       // 빈도수 테이블 값 추가 O(n)
        for(int i = 0; i < n; i++){
            table[data[i]]++;
        }

        // 중복이 없다 = 빈도수 = 1이다 이용
        // O(100000) 의 시간복잡도
        for(int number = 1; number <= MAX_N; number++){ // 데이터는 1이상이므로 1부터 순회한다
            // 1 ~ 10만까지 순서대로 순회(오름차순)으로 순회하기에 데이터도 오름차순으로 삽입되어 정렬할 필요가 없다
            if(table[number] == 1){
                ret.add(number);
            }
        }

        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        // n개의 번호를 차례로 입력
        int n = sc.nextInt();
        int[] data = new int[n];
        for(int i = 0; i < n; i ++){
            data[i] = sc.nextInt();
        }

        // 중복 없는 원소 계산
        ArrayList<Integer> answers = getUniqueElements(data, n);

        // ArrayList 원소들 출력
        for(int i = 0; i < answers.size(); i++){
            int element = answers.get(i);
            if(i > 0){ // 첫 번째 원소가 아니라면 앞에 공백을 추가한다
                writer.write(" ");
            }
            writer.write(String.valueOf(element));
        }

        // BufferedWriter를 비우고 해제
        writer.flush();
        writer.close();

    }
}

위 중복 계산 함수의 시간복잡도는 O(10만) + O(n)의 시간복잡도를 가진다

2. 정렬의 성질을 활용한 풀이

// 정렬의 성질을 이용한 풀이
class Q3C_1{
    public static final Scanner sc = new Scanner(System.in);
    public static final int MAX_N = 100000;

    private static ArrayList<Integer> getUniqueElements(int[] data, int n) {
        ArrayList<Integer> ret = new ArrayList<>();

        Arrays.sort(data); // 데이터 정렬

        for(int i = 0; i < n; i++){
            if( (i == 0 || data[i -1] != data[i]) && (i == n -1 || data[i+1] != data[i])){
                // 왼쪽값과 다르거나, 왼쪽값이 없으면
                // data[i] := 중복이 없는 수가 오름차순으로 주어진다
                ret.add(data[i]);
            }
        }
        return ret;
    }
    public static void main(String[] args) throws IOException {
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        // n개의 번호를 차례로 입력
        int n = sc.nextInt();
        int[] data = new int[n];
        for(int i = 0; i < n; i ++){
            data[i] = sc.nextInt();
        }

        // 중복 없는 원소 계산
        ArrayList<Integer> answers = getUniqueElements(data, n);

        // ArrayList 원소들 출력
        for(int i = 0; i < answers.size(); i++){
            int element = answers.get(i);
            if(i > 0){ // 첫 번째 원소가 아니라면 앞에 공백을 추가한다
                writer.write(" ");
            }
            writer.write(String.valueOf(element));
        }

        // BufferedWriter를 비우고 해제
        writer.flush();
        writer.close();

    }
}

실제로 두 방법을 사용하여 풀어보면 효율상은 첫번째가 좋지만
여러가지 방법을 해보기 위해 여러 풀이를 통해 풀어봤다 :)