[백준] 2529번 : 부등호

문제

2529번: 부등호

 

접근 방식

백트래킹을 사용해 0 ~ 9까지의 수들을 한 번만 사용하며 조합해가면서

주어진 부등호의 순서와 대소관계가 일치하는지 확인해주면 된다.

 

첫 번째 고른 숫자를 제외하고 이후에는 부등호와 이전 숫자와 현재 숫자가

일치하는지 확인해주며 진행하면 된다.

 

모든 숫자를 고른 후에 부등호를 비교하는 것도 상관 없지만

매번 숫자를 고를 때마다 확인하면 중간에 맞지 않는 경우에 멈출 수 있어서 좋다.

 

k가 9인 경우 최대 값이 9876543210이기 때문에 int 타입의 변수로 값을 다루면

오버플로우나 예외가 발생할 수 있으니 이 부분만 조심하면 된다.

 

풀이

public class Main {

	static int k, end;
	static long max = 0, min = Long.MAX_VALUE;
	static String maxStr = "", minStr = "";
	static String[] sign;
	static char[] nums;
	static boolean[] isUsedSign;
	static boolean[] isUsedNum = new boolean[10];

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

		k = Integer.parseInt(br.readLine());
		end = k + 1;

		sign = new String[k];
		isUsedSign = new boolean[k];
		nums = new char[end];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < k; i++) {
			sign[i] = st.nextToken();
		}

		solve(0);

		System.out.println(maxStr + "\n" + minStr);
	}

	static void solve(int size) {
		if (size == end) {
			String s = new String(nums);
			long num = Long.parseLong(s);
			if (max < num) {
				maxStr = s;
				max = num;
			}
			if (min > num) {
				minStr = s;
				min = num;
			}
			return;
		}

		for (int i = 0; i < 10; i++) {
			if (isUsedNum[i]) continue;

			if (size == 0) {
				isUsedNum[i] = true;
				nums[size] = (char)(i + '0');
				solve(size + 1);
				isUsedNum[i] = false;
			}
			else {
				if (isSatisfied(size, i)) {
					isUsedNum[i] = true;
					nums[size] = (char)(i + '0');
					solve(size + 1);
					isUsedNum[i] = false;
				}
			}
		}
	}

	static boolean isSatisfied(int size, int y) {
		int x = nums[size - 1] - '0';
		return (sign[size - 1].equals(">") && x > y) || (sign[size - 1].equals("<") && x < y);
	}
}