BOJ_2529_부등호

1

구분: Brute-force

언어: Java

전략:

• 순열을 이용해 부등호에 넣은 숫자 조합을 생성한다.
• 순열이 생성되면 부등호 조건에 맞는지를 확인한다.
• 조건에 맞는 순열을 숫자로 만들어 최대, 최소값을 구한다. 
• 출력할 때에는 문자열로 변경한다. - 이때, 0이 생략된 숫자를 문자로 변경할때, 0을 추가한다.

---

2. 코드

import java.util.Scanner;
public class Main {
	static int k; //부등호의 전체 개수 
	static String[] boo; //부등호를 담을 string배열
	static int[] comb, num; //순서를 가진 숫자 조합배열, 0~9까지의 숫자배열
	static boolean[] check; //num의 사용여부를 가릴 boolean 배열
	
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		k = scanner.nextInt();
		boo = new String[k];
		comb = new int[k+1];
		for(int i = 0; i<k; i++) {
			boo[i] = scanner.next();
		}
		num = new int[10];
		for(int i = 0; i<10; i++)
			num[i] = i;
		check = new boolean[10];
		
		perm(0);
		
		//string형태로 출력
		
		System.out.println(Long.toString(max)); //최대값출력
		
		String minstr = Long.toString(min);
		
		if(min / (int)(Math.pow(10, k))==0) {//원래 맨 앞이 0인 경우 - 자릿수가 하나 부족하다 따라서 앞에 0을 붙임 
			System.out.print("0"+minstr);
		}
		else
			System.out.println(minstr);
		
	}//main
	
	static long max = Long.MIN_VALUE;
	static long min = Long.MAX_VALUE;
	
	private static void perm(int cnt) {
		
		
		if(cnt == k+1) { //원하는 개수 만큼 숫자를 선택했다
			//맨처음
			int d = comb[0];
			boolean isokay = true; //부등호 조건을 만족하는가 확인하는 boolean
			for(int i = 0; i<k; i++) {
				
				if(boo[i].equals("<")) {  //부등호가 < 인 경우
					if(d>comb[i+1]) {//이전것(d)가 더 큰 경우 - 부등호 만족 X
						isokay = false;
						break;
					}
				}
				
				
				else if(boo[i].equals(">")) {// 부등호가 >인 경우 
					if(d<comb[i+1]) { //부등호를 만족하지 않으면 
						isokay = false;
						break;
					}
				}
				
				d = comb[i+1];
			}
			if(!isokay) {
				return;
			}
			
			//맨 마지막 숫자 확인
			if(boo[k-1].equals("<")) { //부등호 <
				if(d>comb[k]) //만족하지 않아
					isokay = false;
			}
			else {// 부등호 >
				if(d<comb[k]) //만족하지 않아
					isokay = false;
			}
			 
			if(isokay) {// 조건을 만족하는 경우, 최대 최소임을 판정
				long number = makenum(comb); // 숫자 배열을 숫자로 변경
				max = Math.max(number, max); //최대값 체크
				min = Math.min(min, number); //최소값 체크
				return;
			}
			else{
				return;
			}//해당 순열은 조건을 만족하지 않으므로 그냥 지나가 
		}
		
		//순열 생성
		for(int i = 0; i<10; i++) {
			if(check[i]) //이미 사용되었다면 지나가 
				continue;
			comb[cnt] = num[i];
			check[i] = true;
			perm(cnt+1);
			check[i] = false;
		}
		
	}//perm
	
	
	//전체 숫자로 만들어 주기
	private static long makenum(int[] arr) {
		int n = arr.length;
		String str = "";
		for(int i = 0; i<n; i++) {
			str+=Integer.toString(arr[i]);
			
		}
		return Long.parseLong(str);	
	}
	

}

---

3

• 순열을 생성하고, 생성된 것을 이용하는 문제이다. 
• 숫자 배열을 하나의 숫자로 변경하는 함수를 만들었는데, 이 함수가 숫자<->문자열을 반복한다. 다른 방법을 찾고 싶다. 
• 출력시, 맨 앞에 0이 붙는 경우를 잘 고려해야 한다.