[BOJ] 부등호

[2529] 부등호

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

• 부등호 기호 '<'와 '>'가 나열된 수열 A가 있다.
• 기호의 앞 뒤에 한 자리 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다.
• 이 때, 선택된 수는 모두 달라야 한다.
• k개의 부등호 관계룰 모두 만족시키는 (k+1)개 자리의 정수 중에서 최대값과 죄소값을 구하는 문제

 

 

Solution

• 순열을 사용한 문제해결
• input : 2 < >
• 입력으로 주어진 부등호가 '<'와 '>'이고
• 가장 큰 수를 구하는 경우를 생각해봤을 때
• 이 부등호에는 숫자가 총 3개 필요하기 때문에, 가장 큰 숫자인 9, 8, 7로 구성되는 것이 정답임을 알 수 있다.
• 반대로 가장 작은 수를 구하는 경우에는 0, 1, 2로 구성되는 것이 정답이 된다.

 

 

소스코드

import java.util.Scanner;

public class Main {
	static boolean prev_permutation(int[] a) {
		int i = a.length - 1;
		while (i > 0 && a[i - 1] <= a[i]) {
			i -= 1;
		}

		if (i <= 0) {
			return false;
		}

		int j = a.length - 1;
		while (a[j] >= a[i - 1]) {
			j -= 1;
		}

		int temp = a[i - 1];
		a[i - 1] = a[j];
		a[j] = temp;

		j = a.length - 1;
		while (i < j) {
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i += 1;
			j -= 1;
		}
		return true;
	}

	static boolean next_permutation(int[] a) {
		int i = a.length - 1;
		while (i > 0 && a[i - 1] >= a[i]) {
			i -= 1;
		}

		if (i <= 0) {
			return false;
		}

		int j = a.length - 1;
		while (a[j] <= a[i - 1]) {
			j -= 1;
		}

		int temp = a[i - 1];
		a[i - 1] = a[j];
		a[j] = temp;

		j = a.length - 1;
		while (i < j) {
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i += 1;
			j -= 1;
		}
		return true;
	}

	static boolean check(int[] perm, char[] a) {
		for (int i = 0; i < a.length; i++) {
			if (a[i] == '<' && perm[i] > perm[i + 1]) {
				return false;
			}
			if (a[i] == '>' && perm[i] < perm[i + 1]) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		char[] a = new char[k];
		for (int i = 0; i < k; i++) {
			a[i] = sc.next().charAt(0);
		}
		int[] small = new int[k + 1];
		int[] big = new int[k + 1];
		for (int i = 0; i <= k; i++) {
			small[i] = i;
			big[i] = 9 - i;
		}
		do {
			if (check(small, a)) {
				break;
			}
		} while (next_permutation(small));
		System.out.println();
		do {
			if (check(big, a)) {
				break;
			}
		} while (prev_permutation(big));
		for (int i = 0; i < big.length; i++) {
			System.out.print(big[i]);
		}
		System.out.println();
		for (int i = 0; i < small.length; i++) {
			System.out.print(small[i]);
		}
		System.out.println();
	}
}