BOJ 10597번: 순열장난

문제

문제 바로가기> BOJ 10597번: 순열장난

10597번: 순열장난

 

풀이

 

1 ≤ N ≤ 50이므로, 수를 한개  또는 두개 씩 잘라가며, 순열을 만들어 본다!

이 때, 이미 사용한 수, 수열의 범위를 넘어서는 수의 경우는 더 이상 탐색해 볼 필요가 없다.

 

C++

#include<iostream>
#include<vector>
#define MAX 51
using namespace std;

int N, len;
vector<int> v;
bool isuse[MAX];

void solution(string seq){
    if(seq == "") {
        for(int i=0; i<v.size(); i++) cout << v[i] << " ";
        exit(0); // 종료 조건
    }

    int num;
    for(int i=1; i<=2; i++){
        num = stoi(seq.substr(0, i));
        if(num<=len && !isuse[num]){
            isuse[num] = true;
            v.push_back(num);
            solution(seq.substr(i, seq.size()-i));
            isuse[num] = false;
            v.pop_back();
        }
        if(seq.size() == i) break;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    string seq; cin >> seq;
    len = seq.size();
    if(len>9) len -= (len-9)/2;
    solution(seq);
}

 

Java

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

public class Main {
	
	static int N, len;
	static boolean[] isuse;
	static List<Integer> nums = new ArrayList<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String seq = br.readLine();
		len = seq.length();
		if(len>9) len-=(len-9)/2;
		isuse = new boolean[len+1];
		solution(seq);
		br.close();
	}

	private static void solution(String seq) {
		if(seq.equals("")) {
			for(int i=0; i<len; i++) System.out.print(nums.get(i) + " ");
			System.exit(0);
		}
		
	    int num = 0;
	    for(int i=1; i<=2; i++){
	        num = Integer.parseInt(seq.substring(0, i));
	        if(num<=len && !isuse[num]){
	            isuse[num] = true;
	            nums.add(num);
	            solution(seq.substring(i));
	            isuse[num] = false;
	            nums.remove(nums.size()-1);
	        }
	        if(seq.length() == i) break;
	    }
	}
}