지구정복

[재귀] 백준 - 부등호(2529) 본문

데이터 엔지니어링 정복/Algorithm

[재귀] 백준 - 부등호(2529)

eeaarrtthh 2022. 8. 8. 22:38
728x90
반응형

-문제

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

 

2529번: 부등호

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시

www.acmicpc.net

 

-자바 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    static char[] ineq = new char[10];
    static boolean[] visit = new boolean[10];
    static int k;
    static ArrayList ans = new ArrayList<>();

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt( br.readLine() );

        StringTokenizer st = new StringTokenizer( br.readLine() );
        ineq = new char[k];
        for( int i=0; i<k; i++ ) {
            ineq[i] = st.nextToken().charAt(0);
        }

        check( 0, "" );
        Collections.sort( ans );

        System.out.println( ans.get(ans.size()-1) );
        System.out.println( ans.get(0) );
        
    }

    static void check( int idx, String res ) {
        if( idx == k+1 ) {
            ans.add( res );
            return;
        }

        for( int i=0; i<=9; i++ ) {
            if( visit[i] ) continue;

            if( idx==0 || check2( res.charAt(idx-1), (char)(i+'0'), ineq[idx-1] ) ) {
                visit[i] = true;

                check( idx+1, res+Integer.toString(i) );

                visit[i] = false;
            }
        }
    }

    static boolean check2( char prev_char, char res, char ineq_char ) {

        if( ineq_char == '<' ) {
            if( prev_char > res ) { return false; }
        }
        if( ineq_char == '>' ) {
            if( prev_char < res ) { return false; }
        }

        return true;
    }
}
728x90
반응형
Comments