BOJ 2529 - 부등호

2529번: 부등호

아이디어

 

탐색

일단 조건을 생각하지 말고 0~9까지의 숫자를 중복없이 순서있게 나열한다.

 

private static void rec_func(int k) throws IOException {
    if (k == M + 1) {
    	// 조건
        
    } else {
        for (int i = 0; i <= 9; i++) {
            if(visit[i] == 1) continue;

            selected[k] = i;
            visit[i] = 1;

            rec_func(k + 1);

            selected[k] = 0;
            visit[i] = 0;
        }

    }
}

 

조건

완성된 숫자의 조합이 부등호 사이에 들어갔을 때 참인 경우만 ArrayList에 담아준다.

 

private static boolean isvalid() {

    boolean possible = false;

    for (int i = 1; i <= N; i++) {
        // 뒤의 수가 큰 경우 && <
        if (((selected[i] - selected[i + 1]) < 0) && (inequality[i] == '<')) {
            possible = true;

        // 앞의 수가 큰 경우 && >
        } else if (((selected[i] - selected[i + 1]) > 0) && (inequality[i] == '>')) {
            possible = true;
        } else {
            possible = false;
        }

        if (possible == false) {
            break;
        }

    }

    return possible;
}

출력

탐색할 때 오름차순으로 순차적으로 탐색했으므로 ArrayList에 들어간 문자열들도 정렬되어있는 상태일 것이다.

따라서 최대/최소 값은 ArrayList의 끝/처음 값이다.

 

bw.write(result.get(result.size() - 1)+"\n");
bw.write(result.get(0));

 

 

개삽질의 삽질의 삽질의 연속으로 2시간 걸려서 풀었다.. ㅠㅠ

시간복잡도

N의 최댓값은 9이므로 최대 10개의 수를 중복없이 순차적으로 나열한 순열문제라서 아무리 오래 걸려봐야 10! 미만일 것이므로 가능한 접근법이다.

 

구현

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static char[] inequality;
    static int[] selected, visit;
    static ArrayList<String> result = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        input();

        rec_func(1);

        bw.write(result.get(result.size() - 1)+"\n");
        bw.write(result.get(0));
        bw.close();
    }

    private static void rec_func(int k) throws IOException {
        if (k == M + 1) {
            // 조건 : 부등호를 만족하는가 ?
            if (isvalid() == true) {
                String s = "";
                for (int i = 1; i <= M; i++) {
                    s += selected[i];
                }
                result.add(s);

            }

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

                selected[k] = i;
                visit[i] = 1;

                rec_func(k + 1);

                selected[k] = 0;
                visit[i] = 0;
            }

        }
    }

    private static boolean isvalid() {

        boolean possible = false;

        for (int i = 1; i <= N; i++) {
            // 뒤의 수가 큰 경우 && <
            if (((selected[i] - selected[i + 1]) < 0) && (inequality[i] == '<')) {
                possible = true;

            // 앞의 수가 큰 경우 && >
            } else if (((selected[i] - selected[i + 1]) > 0) && (inequality[i] == '>')) {
                possible = true;
            } else {
                possible = false;
            }

            if (possible == false) {
                break;
            }

        }

        return possible;
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = N + 1;

        inequality = new char[N + 1];
        selected = new int[M + 1];
        visit = new int[10];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            inequality[i] = st.nextToken().charAt(0);
        }

    }
}