트리플 소트 - 백준 BOJ 20309

활동중인 교내 ps 모임에서 괜찮은 문제를 하나 공유받았다

알고리즘 풀이글은 왠만하면 포스팅 안하려고 했는데, 생각할거리가 많아서 정리차 한번 적어본다

 

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

20309번: 트리플 소트

 

문제

알고리즘 수업을 듣고 감명받은 윤이는 자신만의 정렬 알고리즘을 만들기로 했다. 윤이가 만든 정렬 알고리즘 "트리플 소트"는 다음과 같이 동작한다.

• 배열에서 연속한 위치에 있는 세 원소를 임의로 고른다.
• 세 원소의 순서를 뒤집는다. 예를 들어 세 원소가 순서대로 a,b,c이면 뒤집은 뒤에는 c,b,a가 된다.
• 배열이 오름차순으로 정렬될 때까지 위 과정을 반복한다.

하지만 윤이는 트리플 소트로 모든 배열을 정렬할 수 없다는 사실을 깨닫고 실망했다. 1부터 N까지의 정수가 한 번씩 등장하는 배열이 주어졌을 때, 트리플 소트로 정렬할 수 있는지 판별하는 프로그램을 작성하시오.

입력

첫 번째 줄에 배열의 크기를 나타내는 정수 N이 주어진다.

두 번째 줄에 배열의 원소가 공백을 사이에 두고 순서대로 주어진다.

출력

트리플 소트로 주어진 배열을 오름차순으로 정렬할 수 있으면 YES, 그렇지 않으면 NO를 출력한다.

 

---

처음 풀이

 

처음에 이 문제를 풀 때 가능한 모든 경우의 수를 전부 다 따져보려고 했었다

index 0 를 시작으로 n - 2 까지 선형적으로 배열을 탐색하면서, 강한 단조증가가 아닐 경우 현재 index 의 원소와 index + 2 의 원소를 swap 했다

매 swap 후 현재 index 까지 배열의 정렬 유무를 확인했으며, 탐색 완료 후 배열 전체의 정렬 유무를 한번 더 따져 트리플 소트의 정렬 가능 유무를 판별하려 했다

 

해당 풀이가 불가능한 이유는 크게 두가지가 있었는데,

 

1. 최악의 경우 시간복잡도가 O(N^2) 으로 90,000,000,000 번 연산을 수행하게 되어 제한시간 1초를 넘어가게 되고
2. 강한 단조증가가 아님이 확인된 index 에 대해, 트리플 소트를 수행 할 index 의 위치 또한 index 말고도 index + 1 의 경우도 따져봐야 했었다

 

30분 넘게 고민해도 문제가 풀리지 않아 정답을 찾아봤다

 

---

정석 풀이

 

• 세 원소가 순서대로 a,b,c이면 뒤집은 뒤에는 c,b,a가 된다
• 1부터 N까지의 정수가 한 번씩 등장하는 배열

 

이 두가지 조건이 풀이의 핵심이었다

 

트리플 소트의 특징으로 인해 어떻게 정렬을 수행해도 각 원소의 index 의 홀수 or 짝수 가 유지되고

1 부터 N 까지의 정수가 한 번씩 등장함으로 인해 각 원소의 홀, 짝 여부는 index 의 홀, 짝 여부와 정확히 반대되게 된다

index		0 1 2 3 4 5
element		1 2 3 4 5 6

// index 가 홀수이면 element 는 짝수이고, 반대도 마찬가지이다

 

따라서 별도의 정렬을 시뮬레이션할 필요 없이, 입력값으로 주어진 배열의 원소들에 대해 각각 index 와의 mod 2 연산 결과의 일치여부를 따져주면 되는 간단한 문제였다

 

import java.io.*;
import java.util.*;
import java.util.stream.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int arrSize = Integer.parseInt(reader.readLine());
        int[] arr = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        for(int i = 0; i < arrSize; i++) {
            if(i % 2 == arr[i] % 2) {
                System.out.println("NO");
                return;
            }
        }

        System.out.println("YES");
    }
}

 

---

배열의 원소들 전부가 임의의 값으로 주어진다면?

 

트리플 소트라는 조건만으론 문제의 풀이가 너무 어려워질걸 생각했는지, 출제자가 1부터 N까지의 정수가 한 번씩 등장하는 배열 이라는 조건을 추가한것이 굉장히 이질적으로 느껴졌다. 이 조건을 제외한다면 이 문제는 어떻게 풀 수 있을까?

 

:(

 

말은 내가 꺼냈지만, 나도 감이 안잡혀서 한번 던져봤다

교내에서 ps 로는 날고기는 분들이 모인 곳이라 그런지 금방 해답을 들을 수 있었다

 

 

1 ~ N 까지 정수가 한번씩 나온다는 조건이 빠졌으니 4 4 4 4 5 와 같은 입력값도 들어올 수 있다

하지만 트리플 소트의 조건은 여전히 유효하므로 위의 입력값으로 부터 도출되는 중간값으로는 다음의 예시와 같은 값들이 나온다

 

4 4 4 4 5
4 4 5 4 4
5 4 4 4 4

 

모든 경우의 수를 살펴보면, 짝수 index 에 있던 원소 5 는 계속 짝수 index 에 머물게 되는걸 볼 수 있다

 

따라서 짝수 index 의 값들과, 홀수 index 의 값들을 분리해서 본다면...

 

index 가 짝수인 원소들을 분리해낸 배열을 정렬하고

index 가 홀수인 원소들도 동일한 작업을 수행 후

두 배열을 병합정렬의 merge 단계를 수행하듯 양 배열에서 번갈아가며 원소들을 꺼내 하나의 배열로 합친 후

입력값으로 주어진 배열들을 정렬한 값과, 위에서 합쳐진 배열을 비교해 두 배열이 동일하다면 YES 를, 아니면 NO 를 출력하게 하면 된다

 

import java.io.*;
import java.util.*;
import java.util.stream.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        int[] arr = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int[] sortedOddIndexedArr = getSortedArrSegment(arr, false);
        int[] sortedEvenIndexedArr = getSortedArrSegment(arr, true);

        Arrays.sort(arr);
        int[] sortedMergedArr = mergeArr(sortedOddIndexedArr, sortedEvenIndexedArr);

        String answer = Arrays.equals(arr, sortedMergedArr) ? "YES" : "NO";
        System.out.println(answer);
    }

    private static int[] getSortedArrSegment(int[] srcArr, boolean isEven) {
        int mod = isEven ? 0 : 1;

        return IntStream.range(0, srcArr.length)
                .filter(i -> i % 2 == mod)
                .map(i -> srcArr[i])
                .sorted()
                .toArray();
    }

    private static int[] mergeArr(int[] oddIndexArr, int[] evenIndexArr) {
        int index = 0;
        int retIndex = 0;

        int[] ret = new int[oddIndexArr.length + evenIndexArr.length];

        while(index < oddIndexArr.length && index < evenIndexArr.length) {
            ret[retIndex] = evenIndexArr[index];
            retIndex++;

            ret[retIndex] = oddIndexArr[index];
            retIndex++;

            index++;
        }

        while(index < evenIndexArr.length) {
            ret[retIndex] = evenIndexArr[index];
            retIndex++;
            index++;
        }

        return ret;
    }
}

 

시간복잡도도 O(NlogN) 으로 시간초과에 걸리지 않고 잘 통과한다 :)