백준 1469 숌 사이 수열 (Java)

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

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int[] ans = new int[25];
    static boolean[] visit = new boolean[25];
    static int[] x;


    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(reader.readLine());

        x = new int[n];

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        for (int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(tokenizer.nextToken());
        }

        Arrays.fill(ans, -1);


        //사전순으로 가장 빠른 배열을 출력해야 하므로 정렬
        Arrays.sort(x);

        dfs(0);

        System.out.println(-1);


    }

    public static void dfs(int depth) {

        if (depth == n * 2) {
            for (int i = 0; i < n * 2; i++) {
                System.out.printf(ans[i] + " ");

            }
            System.exit(0);
        }
        if (ans[depth] != -1) {
            dfs(depth + 1);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visit[i] && depth + x[i] + 1 < n * 2 && ans[depth] == -1 && ans[depth + x[i] + 1] == -1) {
                visit[i] = true;
                ans[depth] = ans[depth + x[i] + 1] = x[i];
                dfs(depth + 1);
                ans[depth] = ans[depth + x[i] + 1] = -1;
                visit[i] = false;
            }
        }

    }


}

1. 문제

숌은 N개의 다른 숫자로 구성되어 있는 집합 X를 만들었다. 그리고, 길이가 2N인 숌 사이 수열 (S)을 만들려고 한다.

숌 사이 수열이란 다음과 같다.

1. X에 들어있는 모든 수는 숌 사이 수열 S에 정확히 두 번 등장해야 한다.
2. X에 등장하는 수가 i라면, S에서 두 번 등장하는 i사이에는 수가 i개 등장해야 한다.

예를 들어, 숌이 만든 집합 X가 {1,2,3}이고, 숌이 만든 숌 사이 수열이 {2 3 1 2 1 3}이라면, 일단 X에 속하는 모든 수가 S에 두 번 등장하므로 1번 조건을 만족한다. 그리고, 2와 2사이엔 수가 두 개, 1과 1사이엔 1개, 3과 3사이엔 3개가 등장하므로 조건을 만족시킨다.

집합 X가 주어졌을 때, 숌 사이 수열 S를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 X의 크기 N이 주어진다. 둘째 줄에 X에 들어가는 수가 빈칸을 사이에 두고 주어진다. X의 크기는 8보다 작거나 같은 자연수이다. X의 원소는 0보다 크거나 같고 16보다 작거나 같은 정수이다.

출력

첫째 줄에 숌 사이 수열을 출력한다. 만약 여러 개일 경우 사전 순으로 가장 빠른 것을 출력한다. 만약 없을 경우에는 -1을 출력한다.

2. 풀이

처음에 해당 문제를 모든 수열을 탐색하여 풀려 했으나 길이가 8인 수열에 대해 너무 오랜 시간이 걸렸다. 그도 그럴게 16자리의 수열을 모두 확인하려면 O(16!)의 시간복잡도가 걸리게 된다. 따라서 좀 더 스마트하게 전수조사를 해야 한다.

 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(reader.readLine());

        x = new int[n];

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        for (int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(tokenizer.nextToken());
        }

        Arrays.fill(ans, -1);


        //사전순으로 가장 빠른 배열을 출력해야 하므로 정렬
        Arrays.sort(x);

우선 필요한 값들을 입력받는다.

"사전순으로 가장 빠른 배열" 여기서 백트래킹을 생각해냈다. 이에 따라 dfs를 사용하여 탐색하고, 받은 배열 x를 정렬한다.

public static void dfs(int depth) {

        if (depth == n * 2) {
            for (int i = 0; i < n * 2; i++) {
                System.out.printf(ans[i] + " ");

            }
            System.exit(0);
        }
        if (ans[depth] != -1) {
            dfs(depth + 1);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visit[i] && depth + x[i] + 1 < n * 2 && ans[depth] == -1 && ans[depth + x[i] + 1] == -1) {
                visit[i] = true;
                ans[depth] = ans[depth + x[i] + 1] = x[i];
                dfs(depth + 1);
                ans[depth] = ans[depth + x[i] + 1] = -1;
                visit[i] = false;
            }
        }

    }

 dfs 파트이다. depth는 숫자의 시작 위치이고(시작 위치와 종료 위치, 그 사이에 숫자만큼의 배열이 들어가야 함) 해당 문제에서는 ans 배열을 -1로 잡고, x의 각 수에 대해, 해당 숫자를 사용하지 않았고, 현재 위치와 현재 위치+해당 숫자+1의 위치(이렇게 하면 숌 사이 수열의 조건을 만족할 수 있음)에 숫자를 배치할 수 있다면 그 수를 각 위치에 집어넣는 방식을 구현했다. 이렇게 하면 배열을 완성했을 때 해당 배열을 검증할 필요가 없게 된다. 

 이를 반복하고, 배열을 완성했다면 ans를 출력하고, 사전 순 가장 빠른 순열만 출력해야 하므로 프로그램을 종료한다.