[java] 정올 - 부등호

문제

정올 - 부등호
주어지는 부등호를 만족하는 수 중 최소값과 최대값을 구하는 문제

• 제한 사항
  부등호의 수 k : 2 <= k <= 9

• 예시
  k = 2, < > 와 같은 2개의 부등호가 주어졌을 때
  0 < 1 > 2 은 부합하지 않음
  0 < 2 > 1 는 가능함
  0 < 2 > 1, 1 < 3 > 2 … 같이 만들 수 있는 경우에서

숫자를 차례로 썼을 때
최소값 : 021 (0 < 2 > 1)
최대값 : 897 (8 < 9 > 7)

풀이

문제를 부등호를 만족하는 순열이라고 이해를 할 수 있다
순열을 만드는 과정에서, 입력받은 부등호에 따라 값을 쳐내면서 진행한다

일반적으로 순열을 만들면 0 ~ 9까지 범위라고 했을때

public void 순열(int idx){
if(idx== maxLen) 	return; 
for(int i=0; i < 10; i++){
	if(!visited[i]){
		visited[i]=true;
		순열(idx+1);
		visit[i]=false;
		}
	}
}

대강 이런식으로 구성을 한다면, for문이 0 ~ 9까지 돌기때문에
가장 첫번째 만들어지는 순열은 (10자리를 만든다면) 0123456789가 된다
그리고 가장 마지막에 만들어지는 결과는 9876543210이다
즉, 생성되는 결과들 중에서 가장 먼저만들어지는게 최소값, 가장 나중에 만들어지는게 최대값이 된다

순열만드는 과정에서 부등호비교를 할 때 비교를 하려면 기본적으로 2개 이상의 값이 되어야한다
숫자 1개를 가지고는 대소비교를 못하니까 ㅠ

내가 짠 코드를 그림으로 보면 아래와 같다

val[i]의 값은 val[i-1]와 flag[i-1]에 의해 결정된다
(flag가 true이면 <, false이면 >)

val을 0부터 시작하면, i-1이 인덱스에 맞지않아서 별도로 처리를 해줘야하기때무에
걍 처음 val[0]의 값은 함수의 밖에서 처리해줬다

// Main함수
for (int i = 0; i < 10; i++) {
	val[0] = i; // 0번째를 미리 지정하고
	use[i] = true;
	dfs(val, 1); // 함수로 들어감
	use[i] = false;
}

0번째 값을 지정한 다음 순열을 1번째 인덱스부터 돌린다(채워준다)
그 결과를 모두 result에 담아서
최대값(가장 마지막에 나온 값), 최소값(가장 첫번째로 얻은 값)을 출력하면 끝 ~~!

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class jung2570_부등호 {

	static boolean[] use = new boolean[10];
	static ArrayList<int[]> result = new ArrayList<>();
	static boolean[] flag;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int k = Integer.parseInt(br.readLine());
		flag = new boolean[k];
		// > : false, < : true
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < k; i++) {
			if (st.nextToken().equals("<"))
				flag[i] = true;
		}
		int val[] = new int[k + 1];

		for (int i = 0; i < 10; i++) {
			val[0] = i;
			use[i] = true;
			dfs(val, 1);
			use[i] = false;

		}
		StringBuilder sb = new StringBuilder();
		// 최대값 출력을 위해 가장 끝 배열 선택
		int[] v = result.get(result.size() - 1);
		for (int i = 0; i <= k; i++) {
			sb.append(v[i]);
		}
		sb.append("\n");
		// 최소값 출력
		v = result.get(0);
		for (int i = 0; i <= k; i++) {
			sb.append(v[i]);
		}
		// 전체출력
		System.out.println(sb.toString());

	}

	private static void dfs(int[] val, int idx) {
		if (idx == val.length) {
			result.add(val.clone());
			return;
		}

		for (int i = 0; i < use.length; i++) {
			if (!use[i]) {
				if (flag[idx - 1] && val[idx - 1] > i) { // <에 맞지않는 경우
					continue;
				} else if (!flag[idx - 1] && val[idx - 1] < i) { // > 에 맞지않는 경우
					continue;
				}
				use[i] = true;
				val[idx] = i;
				dfs(val, idx + 1);
				use[i] = false;
			}
		}
	}

}