백준_부등호_2529

문제 링크

조건

•  k  : 부등호 문자 개수
• 선택된 k+1개의 문자는 모두 달라야 함

 

접근 방법

• depth를 k로 두고 dfs 탐색

 

솔루션

public class Main {
	static int k;
	static boolean[] check;
	static char[] sign;
	static String max, min;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		k = Integer.parseInt(br.readLine().trim());//부등호 문자 개수
		StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
		sign = new char[k];
		
		for(int i = 0; i < k; i++) {
			sign[i] = st.nextToken().charAt(0);
		}
		
		check = new boolean[10];
		max = "0";
		min = "9999999999";
		permu(0, k, new StringBuilder());
		System.out.println(max);
		System.out.println(min);
	}
	
	private static void permu(int cnt, int depth, StringBuilder str) {
		if(cnt > depth) {
			if(max.compareTo(str.toString()) < 0) {//최대값 갱신
				max = str.toString();
			}
			if(min.compareTo(str.toString()) > 0) {//최소값 갱신
				min = str.toString();
			}
			return;
		}
		
		for(int i = 0; i < 10; i++) {
			if(check[i]) continue;//이미 사용한 숫자
			
			if(cnt > 0 && cnt <= depth) {//부등호 조건에 맞지 않은 경우
				if(sign[cnt-1] == '<' && str.charAt(cnt-1) > (char)('0'+i)) continue;
				else if(sign[cnt-1] == '>' && str.charAt(cnt-1) < (char)('0'+i)) continue;
			}
			
			check[i] = true;
			permu(cnt+1,depth,str.append((char)('0'+i)));
			str.deleteCharAt(str.length()-1);
			check[i] = false;
		}
	}

}

 

리뷰

• 처음에 최대값 찾는 dfs와 최소값 찾는 dfs를 숫자 범위를 정해놓고 두 번 탐색함 => 시간이 더 오래걸림(100ms정도..)
• 다른 사람들 풀이를 보니 dfs 탐색으로 나온 모든 결과값을 list에 넣고 문자열 정렬해서 제일 뒤에 값(최대값)과 앞에 값(최소값)을 출력하는 방법도 좋은 것 같음
• 위상정렬로는 어떻게 풀지..?

•