문제 부등호

문제 링크
실버 2
백트래킹 완전탐색

부등호가 제시되고 0~9까지 수에서 선택하여(한번씩만) 순서를 만족시키는 수들 중 최대값과 최소값을 찾아라

입력

부등호의 갯수 K
K개의 부등호 기호

출력

최대 정수
최소 정수
(문자열로)

풀이

1. 10Pk 의 순열들을 찾는다.
=> solve 함수안의 for문과 visited함수를 이용한 방법으로 찾아준다.
모르겠으면 순열 기본문제를 먼저 풀어보자

2. 부등호를 확인하고 for문과 재귀를 처리한다.
=>solve 함수안에서 cnt가 0이 아니라면
부등호를 체크해서 각각 9일때와 0일때의 예외 처리를 해주고
(1) 부등호가 <일때는 i가 이전 숫자보다 작으면 visited에 기록하고 arr2에 기록하는 작업을 거치지않고 다음 i로 바로넘어가준다.(continue)
(2) 부등호가 >일때는 i가 이전숫자보다 크면 이후 for문에서도 i는 더커질것이기때문에 이전숫자를 결정하는 코드로 되돌아간다.
(return)

3. 숫자들을 하나의 정수로 만들어 MAX,MIN을 찾는다.
=> basecase 부분 for문을 이용하여 이전 숫자에 10을 하는 방법으로 하나의 숫자로 만든다.
Math.min과 max를 이용해 최소 최대를 구한다.
주의할점 : 계산한 값이 int범위를 넘어가기때문에 long형으로 선언해줘야한다.

4.만약 맨앞자리가 0이면 0까지 출력해준다
=> max값과 min값을 스트링으로 변형한 후 length 메소드를 이용하여 크기가 k와 같다면 한자리가 부족한것이므로 앞에 0을 추가해준다. 그리고 출력해준다.

코드

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

public class 백준2529 {
	static Scanner scan =new Scanner(System.in);
	static int K;
	static long MIN=Long.MAX_VALUE,MAX=Long.MIN_VALUE;
	static String[] arr;
	static String bigger="<";
	static String smaller=">";
	static boolean[] visited;
	static int[] arr2;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		K=scan.nextInt();
		arr=new String [K+1];
		arr2=new int[K+1];
		visited=new boolean[10];
		for(int i=0;i<K;i++) {
			arr[i]=scan.next();
		}
		
		solve(0);
		String max=Long.toString(MAX);
		String min=Long.toString(MIN);
		if(max.length()==K) {
			max=0+max;
		}
		if(min.length()==K) {
			min=0+min;
		}
		System.out.print(max+"\n"+min);
		
	}
	//10Ck
	public static void solve(int cnt) {
		//basecase
		Long cal=(long) 0; // k글자의 정수
		if(cnt==K+1) {
			for(int j=0;j<K+1;j++) {
				cal=cal*10+arr2[j];
			}
			//min max
			MIN=Math.min(MIN,cal);
			MAX=Math.max(MAX,cal);
			return;
		}
		for(int i=0;i<10;i++) {		
			if(!visited[i]) {
				
				//부등호 확인하고 처리
				if(cnt!=0) {
					if(arr[cnt-1].equals(bigger)) {//a<b일때 
						if(arr2[cnt-1]==9) {//더 커야되는데 9면 return
							return;
						}	
						else if(arr2[cnt-1]>i) {//다음 i까지 continue
							continue;
						}		
					}
					else {
						if(arr[cnt-1].equals(smaller)) {//a>b일때
							if(arr2[cnt-1]==0) {//더 작아야되는데 0이면 return
								return;
							}
							else if(arr2[cnt-1]<i) {//어차피 그다음 i는 더 큰수일테니 return
								return;
							}		
						}
					}
				}
				
				visited[i]=true;
				arr2[cnt]=i;
				solve(cnt+1);
				arr2[cnt]=0;
				visited[i]=false;
			}
		}
		
	}
}