[백준] 2529번 : 부등호 - JAVA [자바]

 

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

2529번: 부등호

---

문제

 

문제를 본 순간 순열을 사용하면 풀릴것 같다는 생각이 들었다.

K는 최대 9까지 나올 수 있으니

9! = 362880 임으로 1억이 안되는 걸로 보아 1초안에 테스트가 가능할 것이라고 생각했다.

또한 순열 로직안에서 1중 for문임으로 362880 x 9 = 3625920 널널하다!

 

내가 푼 로직은 이렇다.

1. K + 1 크기의 0~9까지의 수를 순열로 구한다.

2. 순열을 부등호와 비교하여 가능한지 체크

3. 만약 가능하다면 Min, Max를 비교하고 값을 String 형태로 저장후 출력.

 

아래는 K + 1 크기의 0~9 까지의 수로 만든 순열 기본 코드이다.

static void permutation(int count) {
	if(count == K + 1) {
		System.out.println(Arrays.toString(numbers));
		return;
	}
		
	for(int i = 0; i < 10; i++) {
		
		if(visit[i]) continue;
		
		numbers[count] = i;
		visit[i] = true;
		permutation(count + 1);
		visit[i] = false;
	}
}

 

 

순열이 제대로 동작하는 것을 알 수 있었고, 여기서 단순 구현인 2번로직과 3번로직을 추가해주면 끝이다.

---

전체 코드

public class Main {
	static int K;
	static long min, max;
	static String strMin, strMax;
	static String[] split;
	static int[] numbers;
	static boolean[] visit;

	public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("input.txt"));
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	StringTokenizer st;
    	
    	K = Integer.parseInt(in.readLine());
    	split = in.readLine().split(" ");
    	visit = new boolean[10];
    	numbers = new int[K + 1];
    	min = Long.MAX_VALUE;
    	max = Long.MIN_VALUE;
    	
    	// 수열문제.
    	permutation(0);
    	
    	System.out.println(strMax);
    	System.out.println(strMin);
    }
	
	static void permutation(int count) {
		if(count == K + 1) {
        	// 부등호와 매칭이 된다면 아래 로직을 실행. 
			if(isMatch()) {
				String strNumber = getNumber();
				long number = Long.parseLong(strNumber);
				
				if(min > number) {
					min = number;
					strMin = strNumber;
				}
				
				if(max < number) {
					max = number;
					strMax = strNumber;
				}
			}
			return;
		}
		
		for(int i = 0; i < 10; i++) {
			
			if(visit[i]) continue;
			
			numbers[count] = i;
			visit[i] = true;
			permutation(count + 1);
			visit[i] = false;
		}
	}
	
	static boolean isMatch() {
		for(int i = 0; i < split.length; i++) {
			String arrow = split[i];
			
			if(arrow.equals(">")) {
				if(numbers[i] <= numbers[i + 1]) {
					return false;
				}
			}
			else {
				if(numbers[i] >= numbers[i + 1]) {
					return false;
				}
			}
		}
		
		return true;
	}
	
    // int 배열을 문자열로 변경해주는 메소드. 
	static String getNumber() {
		String number = "";
		for(int i = 0; i < numbers.length; i++) {
			number += Integer.toString(numbers[i]);
		}
		
		return number;
	}
}

 

 

---

결과

 

풀고 난뒤 다른 사람의 풀이를 보니 순열이 아닌 백트레킹 자체로 푸신분들이 많았다.

순열을 구하고 비교하는 것이아니라 백트레킹이후 그때마다 부등호가 맞는지 체크한다면 가지치기가 가능할 것이라고 생각했고 이는 속도와 연결될 것이라고 생각한다.