Baekjoon 1469 숌 사이 수열 JAVA

1469번: 숌 사이 수열

문제

숌은 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을 출력한다.

풀이

DFS를 이용하여 만들 수 있는 모든 경우의 수를 탐색한다.

 

cnt로 단계를 관리해서 n개의 깊이만큼 들어갔는지 확인을 하고 다 만들어 졌다면 ans에 저장한다.

ans를 99로 초기화한 이유는 99는 입력으로 들어오지 않기 때문에 만들어 질 수 없는 값이기에 설정을 했다.

이를 통하여 숌 사이 수열이 만들어 질수 있는지 없는지를 판단한다.

 

숌 사이 수열을 만들때 가장 뒷자리부터 값을 큰 값을 넣어 나가면서 자리 유효성을 판단하는 조건을 삽입한다.

[넣는 위치]와 [넣는 위치 - 선택값]의 자리가 둘다 -1로 사용하지 않는 자리라면 값을 넣고 다음 단계로 넘어가

이 작업을 반복하며 모든 값을 넣어서 S가 유효하다면 현재 만들어져 있는 ans와 비교하여 더 작다면 ans를 최신화 시킨다.

 

자세한 것은 코드 참고

 

코드

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

public class Main {
	static int [] x, s, ans;
	static int n;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		x = new int[n];	// 입력받는 숫자의 집합
		s = new int[n*2];	// 임시로 형성되는 숌 수열
		ans=new int[n*2];	// 최종 정답
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
			x[i]=Integer.parseInt(st.nextToken());
		Arrays.fill(s, -1);	// 방문처리 + 임시저장
		Arrays.fill(ans, 99);	// 최종 저장될 답을 저장
		Arrays.sort(x);	// 입력받은 숫자들을 정렬하여 큰 수를 뒤에서 채우는 방식으로 생성가능한 수열 탐색
		f(0, n-1);
		if(ans[0]==99)	// 만약에 저장된 값이 없다면, 숌 수열이 생성되지 않았기에 -1을 출력
			System.out.println(-1);
		else
			for(int i=0;i<2*n;i++)
				System.out.print(ans[i]+" ");
	}
	
	public static void f(int cnt, int pos) {	// cnt는 숫자들을 하나씩 사용하며 수열을 생성
		if(cnt==n) {
			if(Arrays.compare(ans, s)>0)	// 다양하게 숫자들이 수열들이 생성 될 수 있기에, 만들어진 수열들을 저장하며 사전순으로 가장 빠른것을 최종 답으로 저장
				for(int i=0;i<2*n;i++)
					ans[i]=s[i];
		}
		else {
			for(int j=2*n-1;j>=0;j--) {	// 가장 뒤부터 가장 큰수를 채워나감으로 탐색을 최소화 함
				if(j-x[pos]-1>=0 && s[j-x[pos]-1]==-1 && s[j]==-1) {	// 마지막위치와 그 위치에서 i사이에 수를 i개 두는 위치에 현재 값을 놓을 수 있는지 판단
					s[j]=s[j-x[pos]-1]=x[pos];
					f(cnt+1,pos-1);
					s[j]=s[j-x[pos]-1]=-1;
				}
			}
		}
	}
}