백준 2529 부등호(Silver1)

정답코드

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

public class Main {
	
	static ArrayList<String> result = new ArrayList<>();
	static int N;
	static boolean[] visited;
	static String [] ineq;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		ineq = br.readLine().split(" ");
		
		for(int i = 0; i<10; i++) {
			visited = new boolean[10];
			visited[i] = true;
			DFS(i,0,Integer.toString(i));
			visited[i] = false;
		}
		
		System.out.println(Collections.max(result));
		System.out.println(Collections.min(result));
		
	}
	
	public static void DFS(int num, int depth, String word) {
		//숫자의 길이가 부등호 갯수보다 1개 더 많을 때 & 모든 부등호를 만족하는 경우 리스트에 넣는다 
		if (word.length() == N+1) {
			result.add(word);
			return;
		}
		
		for (int i = 0; i < 10; i++) {
			if(visited[i]==false) {	
				//부등호 방향에 따라 Backtracking 
				if(ineq[depth].equals(">")) {
					if(num>i && !word.contains(Integer.toString(i))) {
						visited[i] = true;
						DFS(i,depth+1,word+i);
						visited[i] = false;
					}
				}
				//부등호 방향에 따라 Backtracking
				else if(ineq[depth].equals("<")){
					if(num<i && !word.contains(Integer.toString(i))) {
						visited[i] = true;
						
						DFS(i,depth+1,word+i);
						visited[i] = false;
					}
				}	
			}
		}
	}
}

전략

• 부등호 input으로 받고 DFS를 이용해서 각 자리수를 depth로 순회시키고 조건따라 백트래킹

• 부등호 조건이 맞지 않을 때 백트래킹을 통해 연산이 안 되도록 구현

• 종료 조건 (처음엔 그냥 depth == N+1로 해서 했는데 제대로 답이 나오지 않음)
  
  

도움 받은 부분

• 원래 나의 의도 0~9까지 배열을 만들고 DFS에 추가될 때 마다 cnt를 늘려 가면서 순서 점검
  • ex) 0 1 2 3 4 5 6 7 8 9
    • 0 0 1 3 2 4 0 0 0 0 이면 2435
  • & 종료 조건에서 value에 따라 정렬하고 합쳐주기
    
    
• 재귀조건에서 String을 넘겨서 더 쉽게 구현할 수 있다는 걸 도움 받음
  • string length가 N+1이면 종료조건