2529_부등호

사용 알고리즘: 백트래킹

사용 언어: java

 

 

 

일단 이 문제는, 입력 받을 때 주의하자! 로직이 맞았는데 입력 처리 잘못해서 시간을 많이 날렸다ㅡㅡ

 

package week21;

import java.io.*;
import java.util.*;

public class Main {
	static char[] arr;
	static int n;
	static String min = "9876543210", max = "0";

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		arr = new char[n];
		String[] s = br.readLine().split(" ");
		for(int i=0; i<n; i++) {
			arr[i] = s[i].charAt(0);
		}
		
		int[] tmp = new int[n+1];
		boolean[] used = new boolean[10];
		backtrack(tmp, used, 0);
		
		System.out.println(max);
		System.out.println(min);
	}

	private static void backtrack(int[] tmp, boolean[] used, int cnt) {
//		System.out.println(cnt);
		if(cnt == tmp.length) {
			String cur = "";
			for(int i=0; i<cnt; i++) {
				cur += tmp[i];
			}
			
			String[] 비교 = {cur, min};
			Arrays.sort(비교);
			if(비교[0].equals(cur)) {
				min = cur;
			}
			
			비교 = new String[] {cur, max};
			Arrays.sort(비교);
			if(비교[1].equals(cur)) {
				max = cur;
			}
			return;
		}
		
		for(int i=0; i<10; i++) {
			if(cnt==0) {
				used[i] = true;
				tmp[cnt] = i;
				backtrack(tmp, used, 1+cnt);
				used[i] = false;
				continue;
			}
			
			int prev = tmp[cnt-1];
			char budeng = arr[cnt-1];
			if(!used[i] && 
					((budeng == '<' && prev < i) 
					|| (budeng == '>' && prev > i))) {
				used[i] = true;
				tmp[cnt] = i;
				backtrack(tmp, used, 1+cnt);
				used[i] = false;
			}
		}
	}

}