2529_부등호 (JAVA)

2529번: 부등호

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static char[] ch;
	static List<String> anslist = new ArrayList<>(); //N+1개 숫자 뽑은 리스트

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		ch = new char[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++){
			ch[i] = st.nextToken().charAt(0);
		}

		int[] num = {0,1,2,3,4,5,6,7,8,9};
		boolean[] visited = new boolean[10];
		List<Integer> result = new ArrayList<>(); //순열과정에서 사용되는 리스트

		permutation(num, result, visited);

		String ans_min = anslist.get(0);
		String ans_max = anslist.get(anslist.size()-1);
		
		System.out.println(makeans(ans_max));
		System.out.println(makeans(ans_min));
	}

	private static void permutation(int[] num, List<Integer> result, boolean[] visited){
		if(result.size() == N+1){
			int cnt = 0;
			for(int i=0; i<N; i++){
				if(ch[i]=='>' && result.get(i)>result.get(i+1))
					cnt++;
				if(ch[i]=='<' && result.get(i)<result.get(i+1))
					cnt++;
				if(cnt==N){
					anslist.add(result.toString());
					return;
				}
			}
		}

		for(int i=0; i<num.length; i++){
			if(!visited[i]) {
				visited[i] = true;
				result.add(num[i]);
				permutation(num, result, visited);

				visited[i] = false;
				result.remove(result.size() - 1);
			}
		}
	}

	private static String makeans(String str){ //[1, 2, 3] -> 123 으로 바꿔주는 함수
		str = str.replaceAll("\\[", "").replaceAll("\\]","");
		str = str.replace(",","").replace(" ", "");
		return str;
	}
}

 

1) 0~9에서 N+1개 숫자를 뽑는 모든 경우에서,

2) 부등호 관계를 만족하는 것들 중

3) 최소/최대를 출력하면 된다.

 

 

 

다시 말하면,

 

1) 0~9에서 N+1개의 숫자를 뽑는 모든 경우 == 10Pn+1 인 순열이다. (중복X, 순서O)

 

2) 부등호 관계를 만족하는 순열과정에서 anslist를 구하고,

 

3) 최소=anslist.get(0), 최대=anslist.get(anslist.size()-1) 를 출력하면 된다.

   이때, 나는 list.toString을 통해서 리스트->스트링으로 바꾸었고, 이는 [1, 2, 3] 형태가 된다.

   그러므로 makeans() 함수를 통해서 [1, 2, 3] -> 123 꼴로 바꾸어 출력했다.