[Java] BOJ2529, 백준 - 부등호

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

2529번: 부등호

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	13353	6792	4638	49.085%

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.

 

<풀이>

숫자를 사용했는지 체크하는 배열: boolean[] arr

부등호를 저장할 배열: String[] eq

가능한 정답을 저장할 문자열: String answer

 

재귀

완료조건: 숫자가 부등호 개수+1개만큼 쌓임

 

종료조건 : 부등호 조건에 어긋날 경우

 

반복조건 1 - 숫자를 사용한 경우: arr[i]를 true로 바꾸고 진행

반복조건 2 - 숫자를 사용하지 않은 경우: 현재 상태에서 그냥 진행하면 됨( > 바꿔주었던 arr[i]를 다시 false로 바꾸고 진행하면 된다)

 

반복(for문): 숫자를 0부터 9까지 사용하기 때문에 for문으로 0부터 9까지 반복

 

종료했을 때는 정답을 저장할 answer배열에 숫자를 쌓아주고,

가장 큰 수와 가장 작은수만 출력하면 되기 때문에 main함수에서 숫자 길이에 맞춰서 출력한다.

 

시간복잡도

각각의 숫자(10개)를 각 자리(k+1, k의 최댓값은 9)에 넣어볼 수 있고,

앞에서 사용한 숫자는 제외하고 사용할 수 있으니

각 자리마다 10개, 9개, 8개, ... , 2개, 1개의 숫자를 사용할 수 있다

최대 시간복잡도 = 10! = 약 350만

일단 시간은 충분하다.

 

소스 코드

import java.io.*;
import java.util.*;

public class Main {
	private static int n;
	private static boolean[] arr;
	private static String[] eq;
	private static String answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		// 숫자를 사용했는지 판단할 arr배열
		arr = new boolean[10];

		// 입력부
		String s = br.readLine();
		answer = "";
		eq = s.split(" ");
		go(0, "");

		// 맨 처음 출력
		System.out.println(answer.substring(answer.length() - 2 - n, answer.length() - 1));
		// 마지막
		System.out.println(answer.substring(0, n + 1));
	}

	private static void go(int idx, String num) {
		// 완료조건: 숫자가 N개 쌓임
		if (idx > n) {
			answer += num + "\n";
			return;
		}

		for (int i = 0; i < 10; i++) {
			if (arr[i])
				continue;

			// 종료조건: 부등호 조건에 어긋남
			if (idx >= 1 && eq[idx - 1].equals(">") && num.charAt(num.length() - 1) - '0' < i)
				return;
			if (idx >= 1 && eq[idx - 1].equals("<") && num.charAt(num.length() - 1) - '0' > i)
				continue;

			arr[i] = true;
			go(idx + 1, num + i);
			arr[i] = false;

		}
	}
}

 

문제가 나랑 맞지 않는건지 모르겠지만 너무 어렵게 풀었다...

다음에 시간 복잡도를 더 줄일 수 있는 방법으로 다시 풀어봐야겠다.