[BOJ 2529] 부등호 (Java)

문제

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

 

풀이

완전 탐색으로 풀었다. 

 

재귀 함수를 호출한다. 

1. 반복문을 이용하여 숫자를 선택한다.

2. 선택한 숫자에 대해 방문 체크를 한다. (visited 배열 사용)

3. 부등호 연산에 부합하는지 체크한다.

4. 선택한 숫자에 대해 방문을 추가한 후, 지금까지 저장해온 문자열에 선택한 숫자를 붙여서 재귀 함수를 호출한다.

5. 재귀 함수의 호출 횟수가 부등호의 개수+1 이 되었을 때, 현재까지 선택한 숫자의 값에 따라 Min, Max를 갱신한다.

 

소스코드

package bruteforce;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ2529 {

    public static String[] arr;
    public static boolean[] visited;
    public static long K, min, max;
    public static String minstr, maxstr;
    public static Stack<Integer> selected;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        arr = new String[N];
        K = N;
        StringTokenizer st= new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = st.nextToken();
        }
        minstr = "";
        maxstr = "";
        min = Long.MAX_VALUE;
        max = Long.MIN_VALUE;
        visited = new boolean[10];
        selected = new Stack<Integer>();
        for(int i = 0; i <= 9; i++){
            selected.push(i);
            visited[i] = true;
            recur(i, 0, String.valueOf(i));
            selected.pop();
            visited[i] = false;
        }

        bw.write(maxstr + "\n");
        bw.write(minstr + "\n");
        bw.flush();
    }
    public static void recur(int prev, int k, String s){
        if(k == K){
            if(max < Long.parseLong(s)){
                max = Long.parseLong(s);
                maxstr = s;
            }
            if(min > Long.parseLong(s)){
                min = Long.parseLong(s);
                minstr = s;
            }
            return;
        }

        for(int cur = 0; cur <= 9; cur ++){
            if(visited[cur]) continue;
            if(arr[k].equals("<")){
                if(prev < cur){
                    selected.push(cur);
                    visited[cur] = true;
                    recur(cur, k+1, s+cur);
                    selected.pop();
                    visited[cur] = false;
                }
            } else if(arr[k].equals(">")){
                if(prev > cur){
                    selected.push(cur);
                    visited[cur] = true;
                    recur(cur,k+1, s+cur);
                    selected.pop();
                    visited[cur] = false;
                }
            }
        }
    }
}