응모

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {

    public static int[] sorted;

    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[] serialNumber = new int[N];
        for(int i = 0; i < N; i ++){
            serialNumber[i] = Integer.parseInt(st.nextToken());
        }
        Set<Integer> violationOfTheRules = new HashSet<>();
        Stack<Integer> members = new Stack<>();
        members.add(-1);
        // 정렬을 해야 함...
        merge_sort(serialNumber);

        for (int j : serialNumber) {
            if (members.peek() == j) {
                violationOfTheRules.add(members.peek());
                members.pop();
            } else {
                if (!violationOfTheRules.contains(j)) {
                    members.add(j);
                }
            }
        }

        for(int i = 1; i < members.size(); i ++){
            System.out.print(members.get(i) + " ");
        }
    }

    private static void merge_sort(int[] serialNumber) {
        sorted = new int[serialNumber.length];
        merge_sort(serialNumber, 0, serialNumber.length - 1);
        sorted = null;
    }

    private static void merge_sort(int[] serialNumber, int left, int right) {
        if(left == right) return;

        int mid = (left + right) / 2;

        merge_sort(serialNumber, left, mid);
        merge_sort(serialNumber, mid + 1, right);

        merge(serialNumber, left, mid, right);
    }

    private static void merge(int[] serialNumber, int left, int mid, int right) {
        int l = left;
        int r = mid + 1;
        int idx = left;
        while(l <= mid && r <= right){
            if(serialNumber[l] > serialNumber[r]){
                sorted[idx] = serialNumber[r];
                idx ++;
                r ++;
            }
            else{
                sorted[idx] = serialNumber[l];
                idx++;
                l++;
            }
        }

        if(l > mid){
            while(r <= right){
                sorted[idx] = serialNumber[r];
                r++;
                idx++;
            }
        }
        else{
            while(l <= mid){
                sorted[idx] = serialNumber[l];
                l++;
                idx++;
            }
        }

        for(int i = left; i <= right; i ++){
            serialNumber[i] = sorted[i];
        }
    }
}

1. 합병정렬(mergeSort)를 사용하여 nlog(N)의 시간복잡도를 가지는 정렬을 사용하였다.

 

2. 규칙을 어긴 사람들을 HashSet의 자료구조에 담는다.(중복으로 응모한 사람들)

 

3. Stack을 이용하여 중복으로 응모한 사람들이 나타날 경우 pop()하면서 HashSet(규칙위반) 에 들어가게 된다. 

(stack을 생성하고 -1을 넣어준 이유는 stack이 비어 있을 경우 stack.peek()하면 에러가 발생하기 때문)

 

4. Stack에 남는 사람들은 한 번 응모를 한 사람들이기 때문에 이 부분을 출력해준다. 

(0번 인덱스에는 -1이 들어가 있기에 1번 인덱스부터 출력해주면 된다)