[2529번] 부등호

문제 기출 : [https://www.acmicpc.net/problem/2529]

 

 

풀이 방법

[백트래킹 : backTracking] 접근   가장 먼저 default 값을 만들자. 최대값의 경우에는 9부터 -1씩 해가면서 채워주고, 최소값의 경우에는 -부터 _1씩 해가면서 채워준다.   이제부터 backTracking 기법을 사용하여 부등호를 만족하는지 체크한다. 부등호를 읽어올 필요없이 그냥 javascript engine을 사용해서 boolean 값을 받기만 하면 된다. 부등호가 만족하지 않는다면 앞의 숫자와 자리를 바꿔준다. 왜냐하면 최대값과 최소값을 구해야하기 때문이다.   이런식으로 체크를 끝까지 하게 되었을 때 나온 값이 바로 최대값 최소값이 될 수 있다.   단 한 번의 backTracking으로 최대값과 최소값을 구할 수도 있을 것 같은데... 좋은 방법이 떠오르지 않는다...ㅠ

 

문제 풀이

public class Main {
	public final static ScriptEngineManager MNG = new ScriptEngineManager();
	public final static ScriptEngine ENGIN = MNG.getEngineByName("js");
	
	public static void backTracking(char[] input) throws ScriptException {
		String expression = "";
		int frontIndex = 0;
		int hindIndex = 0;
		char temp = ' ';
		String ans = "";
		
		for (int i = input.length-1; i >= 0; i-=2) {
			if(i == 0) {
				System.out.println(ans);
				return;
			}
			
			frontIndex = i-2;
			hindIndex = i;
			for (int j = i-2; j < i+1; j++) {
				expression = expression.concat(String.valueOf(input[j]));
			}
			
			if(false == Boolean.valueOf(String.valueOf(ENGIN.eval(expression)))) {
				temp = input[frontIndex];
				input[frontIndex] = input[hindIndex];
				input[hindIndex] = temp;
				backTracking(input);
				return;
			} else {
				ans = "";
				for (int k = 0; k < input.length; k+=2) {
					ans = ans.concat(String.valueOf(input[k]));
				}
			}
			
			expression = "";
		}
		
	}

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

		try {
			int N = Integer.parseInt(br.readLine());
			int i = -1;
			int j = 10;
			char[] maxInput = new char[(2 * N) + 1];
			char[] minInput = new char[(2 * N) + 1];
			
			StringTokenizer tokens = new StringTokenizer(br.readLine(), " ");

			while (tokens.hasMoreTokens()) {
				i++;
				if(i%2 == 1) {
					char getInput = tokens.nextToken().charAt(0);
					maxInput[i] = getInput;
					minInput[i] = getInput;
				} else {
					j--;
					maxInput[i] = Character.forDigit(j, 10);
					minInput[i] = Character.forDigit(9-j, 10);
				}
			}
			maxInput[maxInput.length-1] = Character.forDigit(j-1, 10);
			minInput[minInput.length-1] = Character.forDigit(9-(j-1), 10);
						
			backTracking(maxInput);
			backTracking(minInput);

		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}