BOJ 1071 소트

https://www.acmicpc.net/problem/1071

문제

N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다.

---

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. N개의 수는 1,000보다 작거나 같은 자연수 또는 0이다.

---

출력

첫째 줄에 문제의 정답을 출력한다.

---

예제 입력 1

3
1 2 3

예제 출력 1

1 3 2

예제 입력 2

9
1 1 1 1 2 2 2 2 2

예제 출력 2

2 2 2 2 2 1 1 1 1

… 이하 예제 생략

---

코드

이번 문제는 배열에서 두 원소를 swap 할 때, 비트 연산자를 사용해 swap 해보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] inputs;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        inputs = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            inputs[i] = Integer.parseInt(st.nextToken());

        // 사전 순이기 때문에 일단 입력받은 수들을 정렬시켜준다.
        Arrays.sort(inputs);

        for (int i = 0; i < N - 1; i++) {
            // 현재 검사 중인 수가 다음 수와 연속된 수가 아니면, 다음 수 검사
            if(inputs[i] + 1 != inputs[i + 1]) continue;

            /**
             * 현재 검사 중인 수가 다음 수 a와 연속된다면
             * a 이후에 나오는 수 중 a와 같지 않은 수를 a와 swap 한다.
             */
            boolean flag = false;
            for (int j = i + 2; j < N; j++) {
                if(inputs[i + 1] != inputs[j]) {
                    flag = true;
                    swap(i + 1, j);
                    break;
                }
            }

            /**
             * 만약 swap 하지 못했을 경우는 a 이후에 있는 수는 모두 a와 같은 수 이기 때문에
             * 검사 중인 수 앞에 나온 수 들 중에서
             * 검사 중인 수와 같지 않은 수와 검사 중인 수를 swap 한다.
             */
            if(!flag) {
                int target = 0;
                for (int j = i - 1; j >= 0; j--) {
                    if(inputs[j] != inputs[i]) {
                        target = j + 1;
                        break;
                    }
                }
                swap(target, i + 1);
            }
        }

        // 문제에 만족하는 상태로 정렬된 수들을 정답으로 출력
        StringBuilder answer = new StringBuilder();
        for (int i: inputs) answer.append(i).append(' ');
        System.out.println(answer);
    }

    static void swap(int idx1, int idx2) {
        inputs[idx1] ^= inputs[idx2];
        inputs[idx2] ^= inputs[idx1];
        inputs[idx1] ^= inputs[idx2];
    }
}