[백준 2529, Java] 부등호

문제

www.acmicpc.net/problem/2529

2529번: 부등호

 

풀이

 부등호가 N개 있으면 숫자는 N+1개를 뽑아야 한다. 이때 숫자는 중복을 허락하지 않는 수라고 했으므로 N과 M(1)과 같은 문제다.  중복되지 않는 수 N+1개를 뽑았다면, 입력받은 부등호와 비교를 한다. 

 

 비교를 하고 부등호 수열인 경우, int배열에 있는 숫자를 StringBuffer로 변환한 뒤 ArrayList<String> validArray에 add하였다. 

 

 validArray를 정렬하고 나서 맨 앞에 있는 값이 최소값이고, 맨 뒤에 있는 값이 최댓값이된다. 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    static int N;
    static String[] operations;
    static int[] numArray;
    static boolean[] isPicked;
    static ArrayList<String> validArrays;
    static int min;
    static int max;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        operations = new String[N];
        numArray = new int[N+1];
        validArrays = new ArrayList<>();
        isPicked = new boolean[10];
        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;

        st = new StringTokenizer(br.readLine()," ");
        for(int index = 0; index<N; index++){
            operations[index] = st.nextToken();
        }

        // 0~ 9까지 N+1개 뽑기
        pickNum(0);
        Collections.sort(validArrays);
        bw.write(validArrays.get(validArrays.size()-1)+"\n");
        bw.write(validArrays.get(0));
        bw.flush();
    }
    public static void pickNum(int pickedCount){
        if(pickedCount>=N+1){

            //부등호 순서열 검증
            boolean isValid = true;
            for(int index = 0; index<operations.length; index++){
                String operation = operations[index];
                int num1 = numArray[index];
                int num2 = numArray[index+1];

                if(">".equals(operation)){
                    if(num1<num2){
                        isValid = false;
                        break;
                    }
                }
                else{
                    if(num1>num2){
                        isValid = false;
                        break;
                    }
                }
            }

            if(isValid){
                StringBuffer validArray = new StringBuffer();
                for(int index = 0; index<numArray.length; index++){
                    validArray.append(numArray[index]);
                }
                validArrays.add(validArray.toString());
            }
        }
        else{
            for(int num = 0; num<=9; num++){
                if(!isPicked[num]){
                    isPicked[num] =true;
                    numArray[pickedCount] = num;

                    pickNum(pickedCount+1);
                    isPicked[num] = false;

                }
            }
        }
    }
}