[자바] 백준 2529번: 부등호

https://www.acmicpc.net/problem/2529

2529번: 부등호

 

---

모든 경우의 수를 확인해서, 부등호 조건이 맞는 경우에 최솟값과 최댓값을 계산하면 될 것 같았다.

 

앞에서 어떤 수를 선택하느냐에 따라 뒷자리 경우의 수가 달라지기 때문에

순열 알고리즘을 응용했다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P2529 {

	static String[] inequality_signs;
	static int k;

	static StringBuffer sb_num = new StringBuffer();
	static boolean[] visited = new boolean[10];
	static long max_num;
	static long min_num = Long.MAX_VALUE;

	static StringBuffer max_str;
	static StringBuffer min_str;

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

		inequality_signs = new String[k];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < k; i++) {
			inequality_signs[i] = st.nextToken();
		}

		perm(0, k + 1);
		System.out.println(max_str);
		System.out.println(min_str);

	}

	static void perm(int i, int n) {
		if (i == n) {
			long num = Long.parseLong(sb_num.toString());

			if (max_num < num) {
				max_num = num;
				max_str = new StringBuffer(sb_num);
			}
			if (min_num > num) {
				min_num = num;
				min_str = new StringBuffer(sb_num);
			}
			return;

		} else if (i == 0) {
			for (int j = 0; j < 10; j++) {
				visited[j] = true;
				sb_num.append(j);
				perm(i + 1, n);
				visited[j] = false;
				sb_num.deleteCharAt(i);
			}
		} else {
			for (int j = 0; j < 10; j++) {
				if (visited[j] == false) {
					String sign = inequality_signs[i - 1];
					int previous_num = sb_num.charAt(i - 1) - '0';
					if ((sign.equals(">") && previous_num > j) || (sign.equals("<") && previous_num < j)) {
						sb_num.append(j);
						visited[j] = true;
						perm(i + 1, n);
						sb_num.deleteCharAt(i);
						visited[j] = false;
					}
				}
			}
		}
	}
}

 

문제를 풀면서 시행착오를 많이 겪었다

부등호를 char배열에 넣고싶었는데, StringTokenizer로 구분하면 결과로 String의 형태로 나오기 때문에

그냥 String배열을 만들어서 사용했다

 

k값으로 8까지는 잘 작동되는데 9에서 오류가 생겼다

확인해보니 Int형 범위를 넘어가는 것이 문제였다

그래서 num을 모두 long타입으로 바꿨다.

 

max_str, min_str은 숫자의 맨 앞자리에 오는 0을 무시하지 않기 위해서 String형태로 따로 저장하기 위해 사용했다.