4회차 - 알고리즘 기록 : 응모

📌응모

  어느 한 아이돌 그룹의 팬 클럽 '아재리눅스'의 회원들은 앨범과 기념품 구매에 돈을 아끼지 않기로 유명하다.

이 아이돌 그룹의 소속사는 이번 새 2집 리패키지 앨범을 구매한 회원들을 대상으로 팬 사인회를 진행하기로 결정하였다.

예상과 같이 새 앨범은 출시와 동시에 엄청난 수량이 판매되었으며, 팬 사인회에서 수용할 수 있는 구매자의 수를 아득히 넘어섰다. 

 결국 모든 회원을 팬 사인회에 초청할 수 없었기에 판매 된 앨범의 시리얼 번호를 통하여 추첨을 하기로 하였다.

하지만 앨범을 구매한 모든 사람이 팬 사인회 참가가 가능한 것은 아니므로 참가를 희망하는 팬들에게 본인이 구매한 앨범의 시리얼 넘버를 통해 응모할 수 있도록 하였다.

 하지만 너무나도 아이돌을 만나고 싶어하는 몇몇 삼촌 팬이 같은 시리얼 번호로 여러 번 응모했다는 사실이 밝혀지면서, 이 아이돌의 매니저인 당신은 중복 응모한 시리얼 넘버를 추첨 대상에서 제외하기로 결정하였다.

하지만 응모한 사람이 너무 많은 나머지 도저히 눈과 손으로는 중복을 제거할 수 없었다.

하지만 현재는 매니저이지만, 왕년에 컴퓨터공학과를 졸업한 당신은 프로그램을 작성해 이 문제를 해결하고자 한다.

응모한 모든 시리얼 번호가 주어질 때, 이 시리얼 번호들 중 두 번 이상 응모한 번호를 모두 제거하여 오름차순으로 출력하는 프로그램을 작성해보자.

 

 

입력 형식

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

한 줄에 응모한 시리얼 번호들이 공백으로 구분된 1이상 10만 이하의 자연수로 주어진다.

 

출력 형식

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

 

예시

- 입력

6

2 3 3 4 7 5

 

- 출력

2 4 5 7

 

코드 풀이

/**
 * data[0] ~ data[n-1]에서 중복이 존재하지 않는 원소들을 반환한다.
 * 단, 각 원소들은 오름차순으로 정렬되어 있어야 한다.
 * @param data  data[0] ~ data[n-1]에는 10만 이하의 자연수다.
 * @param n
 * @return
 */
public 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] ) ){

            // 중복이 존재하지 않는.
            ret.add(data[i]);
        }
    }
    return ret;
}