[백준 2529번] 부등호 - (java)

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

 

📌 문제 탐색하기

선택한 숫자가 모두 달라야 하기 때문에 순열을 이용할 수 있다. 

부동호에 들어갈 숫자를 선택하는게 아니라 숫자를 선택한뒤 그 숫자를 부등호 기호에 맞게 나열해도 된다.

따라서 K+1 개의 숫자를 선택해서 순열을 이용해 숫자들을 나열할 수 있고 부등호 기호에 맞게 나열된 순열중에 가장 큰 값과 가장 작은 값을 찾으면 된다. 

이때 만들수 있는 최솟값은 가장 작은 값들을 선택했을때 나오고 최댓값은 가장 큰 값들을 선택했을때 나온다.

따라서 최솟값은 숫자 0,1,2,3,... 을 선택했을때, 최댓값은 9,8,7,... 을 선택했을때 만들 수 있다.

 

📌 코드 설계하기

1. k의 수와 부등호 문자열을 입력받고 최댓값과 최솟값을 구하기 위해 배열을 두개 선언했다.

2. 숫자의 길이만 지정이 되면 사용할 숫자는 정해지기 때문에 for문을 통해서 사용할 가장 작은 값 k+1 개와 가장 큰 값 k+1개를 베열에 저장했다.

3. 위에서 지정한 숫자 배열로 가능한 순열을 만든다.

4. 만든 순열이 부등호를 만족하는지 확인한다. -> do-while 문을 통해 만족할때 까지 반복

 

📌 풀이

import java.util.Scanner;

// 부등호
public class Main {

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

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

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

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

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

	}

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

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

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

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

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

	static boolean check(int[] perm, char[] sign) {
		for (int i=0; i<sign.length; i++) {
			if (sign[i] == '<' && perm[i] > perm[i+1]) {
				return false;
			}
			if (sign[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[] arr = new char[k];
		for (int i = 0; i < k; i++) {
			arr[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(big, arr)) {
				break;
			}
		} while (permutation1(big));

		// 최솟값
		do {
			if (check(small, arr)) {
				break;
			}
		} while (permutation2(small));


		for (int j : big) {
			System.out.print(j);
		}
		System.out.println();

		for (int j : small) {
			System.out.print(j);
		}

	}
}