[JAVA] 백준 2529번 부등호

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

2529번: 부등호

 

💡 순열 코드를 작성할 수 있는지가 가장 중요!

 

문제 해결 과정

1. 순열을 통해 k+1개의 수 조합

2. 순열을 만들면서 부등호 판별(checkSign)하여 가지치기

3. 기저 조건에 도달하면 만들어진 수를 문자열로 만들어 list에 저장

 

시행착오

1. int형 min, max에 최소, 최댓값을 저장했으나 int 범위를 초과하는 결과값이 있었다.

-> long으로 변경

2. 문제의 출력 조건이다.

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

 사실 처음에는 정수형 min이 1,000,000,000 보다 작으면 출력할 StringBuilder에 "0"+min을 넣어 출력값을 보정해줬다. 자꾸 틀린 이유였다. 출력 정수는 하나의 문자열이여야 한다는 조건이 있었고 간과했다. 

-> ArrayList에 부등호를 만족하는 모든 결과값을 문자열로 만들어 저장했다. 그 후 리스트를 정렬하여 첫번째(최댓값)과 마지막(최솟값)을 출력했다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
    
    static int k;
    static char[] signs;
    
    static int[] src = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    static int[] tgt;
    static boolean[] isSelected = new boolean[src.length];
    
    static ArrayList<String> ans = new ArrayList<>();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        signs = new char[k];
        tgt = new int[k+1];
        
        // input sign of inequalities
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<k; i++) signs[i] = st.nextToken().charAt(0);
        
        // permutation
        perm(0);
        
        // sort & print
        Collections.sort(ans);
        StringBuilder sb = new StringBuilder(ans.get(ans.size()-1)+"\n"+ans.get(0));
        System.out.println(sb);
        
    }
    
    static void perm(int idx) {
        // 기저조건
        if(idx == tgt.length) {
            ans.add(makeNum());
            return;
        }
 
        for(int i=0; i<src.length; i++) {
            if(isSelected[i]) continue;
            
            // 부등호 판별
            if(idx>0 && !checkSign(idx, src[i]))    continue;
            
            isSelected[i] = true;
            tgt[idx] = src[i];
            perm(idx+1);
            isSelected[i] = false;
        }
    }
    
    static boolean checkSign(int idx, int num) {
        if(signs[idx-1]=='<') return tgt[idx-1] < num;
        else return tgt[idx-1] > num;
    }
    
    static String makeNum() {
        StringBuilder tmp = new StringBuilder();
        
        for(int i=0; i<tgt.length; i++) {
            tmp.append(tgt[i]);
        }
        
        return tmp.toString();
    }
}