[백준] 2529. 부등호 (Java)

 

문제

2529번: 부등호

 

알고리즘

브루트포스

 

풀이

N이 최대 9이므로 10개의 숫자로 중복되지 않게 순서를 정하는 순열이라고 생각할 수 있다.

따라서 경우의 수는 10! = 3,628,800 개이므로 모든 경우의 수를 확인할 수 있다.

 

순열을 통해 N + 1자리 숫자를 만들고,

i 번째 자리 숫자와 i + 1 번째 자리 숫자를 i번째 부등호 규칙과 맞는 지 비교한다.

모든 자리 숫자가 규칙을 만족한다면 max, min 과 비교하여 갱신한다.

 

* 정답 숫자가 0부터 시작할 수 있기 때문에 정수 자료형을 사용하면 출력할 때 0부터 시작하는 수를 올바르게 출력할 수 없다. 따라서 max, min을 문자열로 저장한다.

이 경우 max = "99", min = "00" 으로 초기화한다.

 

코드

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

public class Main {
	static int N, selected[];
	static String max, min;
	static boolean[] visited;
	static char[] parens;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		parens = new char[N];
		selected = new int[N + 1];
		visited = new boolean[10];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++)
			parens[i] = st.nextToken().charAt(0);
		
		max = "00";
		min = "99";
		
		perm(0);
		
		System.out.println(max);
		System.out.println(min);
	}

	private static void perm(int count) {

		if (count == N + 1) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < N; i++) {
				if (parens[i] == '<' && selected[i] >= selected[i + 1])
					return;
				else if (parens[i] == '>' && selected[i] <= selected[i + 1])
					return;

				sb.append(selected[i]);
			}
			sb.append(selected[N]);

			max = max.compareTo(sb.toString()) < 0 ? sb.toString(): max; 
			min = min.compareTo(sb.toString()) < 0 ? min: sb.toString(); 
			return;
		}

		for (int i = 0; i < 10; i++) {
			if (!visited[i]) {
				visited[i] = true;
				selected[count] = i;
				perm(count + 1);
				visited[i] = false;
			}
		}
	}
}