백준 2529 부등호 (Java)

1. 문제 링크

2529번: 부등호

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. k+1개를 뽑아서 순열을 만든다.

2. 순열에서 나온 숫자들을 부등호랑 비교하면서 완탐한다

3. 처음부터 시작해서 최솟값을 찾고, 뒤에서부터 시작해서 최댓값을 찾는다.

 

경우의 수가 너무 많아서 각 자리별로 최소 이정도는 와야한다의 수를 찾고 싶었는데,

< > 랑 > < 의 경우에 탐색 순서가 달라서 포기했다..

 

4. 코드

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

//45분
public class Main {
	static int N;
	static String[] bracket;
	static boolean visit[], flag;
	static int[] numbers;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		bracket = br.readLine().split(" ");
		visit = new boolean[10];
		numbers = new int[N+1];
		flag = false;
		reverse_permutation(0);
	
		visit = new boolean[10];
		flag = false;
		permutation(0);
	}
	
	private static boolean check(int[] numbers) {
		for(int i=0;i<N;i++) {
			String now = bracket[i]; //지금 부등호
			if(now.equals("<")) {
				if(numbers[i]>numbers[i+1]) {
					return false;
				}
			}
			else {
				if(numbers[i]<numbers[i+1]) {
					return false;
				}
			}
		}
		return true;
	}

	
	private static void permutation(int cnt) {
		if(cnt == N+1) {
			if(check(numbers)) {
				flag = true;
				for(int i=0;i<cnt;i++) {
					System.out.print(numbers[i]);
				}
				System.out.println();
			}
			return;
		}
		for(int i=0;i<10;i++) {
			if(visit[i]) {
				continue;
			}
			numbers[cnt] = i;
			visit[i] = true;
			permutation(cnt+1);
			if(flag) return; 
			visit[i] = false;
			
		}
	}
	private static void reverse_permutation(int cnt) {
		if(cnt == N+1) {
			if(check(numbers)) {
				flag = true;
				for(int i=0;i<cnt;i++) {
					System.out.print(numbers[i]);
				}
				System.out.println();
			}
			return;
		}
		for(int i=9;i>=0;i--) {
			if(visit[i]) {
				continue;
			}
			numbers[cnt] = i;
			visit[i] = true;
			reverse_permutation(cnt+1);
			if(flag) return;
			visit[i] = false;
			
		}
	}
}