[Baekjoon] 2529_부등호

Silver I

문제(출처: https://www.acmicpc.net/problem/2529)

---

< 부등호 >

 

문제 풀이 

 

만들 수 있는 모든 조합을 구하면서 부등호에 만족하는 값만 다음 값으로 넘겨준다.

 

 my solution (Java)

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

public class _2529_ { // 부등호
	static int num[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	static char arr[];
	static int result[];
	static boolean visited[];
	static String max, min;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int k = Integer.parseInt(bf.readLine());

		arr = new char[k];
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < k; i++) {
			arr[i] = st.nextToken().charAt(0);
		}

		result = new int[k + 1];
		visited = new boolean[10];
		max = "-1";
		min = "100000000000";

		search(0, k);

		bw.write(max+"\n"+min);
		bw.flush();
	}

	private static void search(int idx, int k) {
		if (idx == k + 1) {
			String answer = "";
			for (int i = 0; i < k + 1; i++) {
				answer += result[i];
			}
			if (Long.parseLong(max) < Long.parseLong(answer)) {
				max = answer;
			}
			if (Long.parseLong(min) > Long.parseLong(answer)) {
				min = answer;
			}
			return;
		}
		for (int i = 0; i < 10; i++) {
			if (!visited[i]) {
				if (idx == 0) {
					result[idx] = num[i];
					visited[i] = true;
					search(idx + 1, k);
					visited[i] = false;
				} else {
					if (arr[idx - 1] == '<') {
						if (result[idx - 1] < num[i]) {
							result[idx] = num[i];
							visited[i] = true;
							search(idx + 1, k);
							visited[i] = false;
						}
					} else if (arr[idx - 1] == '>') {
						if (result[idx - 1] > num[i]) {
							result[idx] = num[i];
							visited[i] = true;
							search(idx + 1, k);
							visited[i] = false;
						}
					}
				}
			}
		}
	}
}

변수)
num : 0~9까지 저장한 배열
arr : 부등호 정보
result : 조합
visited : 방문 여부
max, min : 최대, 최소 정수
k : 부등호 문자의 개수

 

max와 min 값은 조합으로 만들 수 없는 -1과 100000000000 값으로 초기화시켜 준다. 모든 변수를 초기화시킨 후 search 함수를 호출한다.

 

0부터 9까지의 숫자를 전체 탐색하며 아직 사용하지 않은 값인지 확인한다. 아직 사용하지 않았으며 첫 번째 값이라면 어떤 숫자던지 넣을 수 있으므로 값을 넣고 다음 값을 구하기 위해 search 함수를 호출한다. 첫 번째 값이 아니라면 부등호를 보고 부등호 조건에 일치할 경우 다음 search 함수를 호출한다.

조합을 사용하여 k+1개의 숫자를 다 구했다면 max와 min 값과 비교하여 값을 교체한다.

 

최종 max와 min 값을 출력한다.

---

---