[백준_2529번] 부등호

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

2529번: 부등호

[문제]

 두 종류의 부등호 기호 ‘<’와 ‘>’가 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 이다. 

 

[코드]

import java.util.*;

public class BaekJoon_2529 {
	public static boolean[] visited=new boolean[10];
	public static char[] sign;
	public static int k,min=Integer.MAX_VALUE;
	public static ArrayList<String> result=new ArrayList<>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		k=sc.nextInt();
		sign=new char[k];
		
		for(int i=0;i<k;i++)
			sign[i]=sc.next().charAt(0);
		
		dfs(0,"");
		
		Collections.sort(result);
		System.out.println(result.get(result.size()-1)); // 가장 큰 숫자
		System.out.println(result.get(0)); // 가장 작은 숫자
	}
	
	public static void dfs(int depth, String num) {
		/*
		 * 부등호가 k개라면 숫자는 k+1개이기 때문에
		 * 깊이가 숫자의 개수와 같아지면 결과를 result에 저장하고 return 
		 */
		if(depth==k+1) {
			result.add(num);
			return;
		}
		
		for(int i=0;i<=9;i++) {
			// 사용했던 숫자가 아니라면
			if(visited[i]==false) {
				/*
				 * 부등호 조건을 만족하거나, 깊이가 0인 경우도 아래 문장 수행
				 * 이때 깊이가 0일 경우에는 부등호 조건의 참/거짓 여부를 판단할 수 없기 때문에
				 * 아래 조건을 반드시 수해해야 하는 depth==0인 경우를 반드시 명시해주어야 한다.
				 */
				if(depth==0||check(Character.getNumericValue(num.charAt(depth-1)),i,sign[depth-1])) {
					visited[i]=true;
					dfs(depth+1,num+Integer.toString(i));
					visited[i]=false;
				}
			}
		}
	}
	
	// 부등호 조건을 만족하지는 검사하는 함수
	public static boolean check(int a, int b, char c) {
		if(c=='>') 
			if(a<b)
				return false;
		
		if(c=='<')
			if(a>b)
				return false;
		
		return true;
	}
}

 

[고찰]

 이번 문제 또한 백트래킹 문제이다. 사용한 문자를 체크하기 위해 visited 배열을 사용하여 이전에 사용한 숫자가 아니고, 부등호 조건을 만족하는 모든 경우의 수를 연결리스트에 저장한 후 연결리스트를 정렬하여 최대, 최솟값을 구하면 된다. 이때 주의해야할 재귀호출을 해주는 조건이 이전에 사용한 숫자가 아니고, 부등호 조건을 만족하며, 재귀의 깊이가 0일 경우도 생각해주어야 한다. 마지막 조건을 명시하지 않으면 깊이가 0일 경우는 비교할 대상이 없어 부등호 조건을 만족할 수가 없어 함수가 시작될 수 없다. 해당 조건을 빠뜨려 오류가 났었는데 고민 끝에 수정할 수 있었다.