[백준] 2529 부등호 - Backtracking / Java

• 문제 링크

2529번: 부등호

 

• 풀이 과정

방문 여부를 확인할 boolean 배열을 활용하는 재귀 함수로 모든 순열을 확인하되,

입력으로 주어진 부등호에 맞는 다음 수를 선택하는 함수로 검사하여 다음 수를 결정한다.

 

이전 인덱스의 수와 현재의 수가 부등호 조건에 맞을 경우에 String 변수에 더하는 방식이며

String 변수의 길이가 비교할 수의 크기와 같을 때 해당 분기 탐색이 완료되었으므로 List 에 더한다.

 

자연스럽게 모든 순열 중 최대값은 List 의 마지막 인덱스에 위치할 것이고 최소값은 첫번째 인덱스이므로

그 두 인덱스의 값을 추출하여 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;

public class Main {

	static int n;
	static char[] sign;
	static boolean[] visit = new boolean[10];
	static List<String> result = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(br.readLine());
		sign = br.readLine().replaceAll(" ", "").toCharArray();

		recur("", 0);

		bw.write(result.get(result.size() - 1) + "\n" + result.get(0));
		bw.flush();
	}

	private static void recur(String num, int idx) {
		if (idx == n + 1) {
			result.add(num);
			return;
		}

		for (int i = 0; i <= 9; i++) {
			if (visit[i])
				continue;

			if (idx == 0 || compare(num.charAt(idx - 1) - '0', i, sign[idx - 1])) {
				visit[i] = true;
				recur(num + i, idx + 1);
				visit[i] = false;
			}
		}
	}

	private static boolean compare(int prev, int now, char sign) {
		if (sign == '<')
			return prev < now;
		else
			return prev > now;
	}

}