[BOJ] 백준 2529 - 부등호 풀이

1. 문제

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

2529번: 부등호

 

2. 풀이

백준 실버 1에 해당하는 브루트포스, 백트래킹에 대한 문제이다. 브루트포스를 연습하려고 손을 댄 문제였지만, 백트래킹에서 한참을 고생하고 다시 개념부터 돌아가게 된 문제였다.

푸는 방법은 여러가지가 있겠지만, 필자는 여기서 다음과 같은 방법을 사용하였다.
우선 입력을 보면 부등호의 개수와 각 부등호가 주어진다. 이때 이 부등호와 숫자가 들어갈 수 있는 공간을 생각해보자.
부등호가 2개라면 그 사이사이 숫자는 3개가 들어간다. 예제 입력 2를 보면 부등호의 개수가 9개일 때 들어갈 수 있는 숫자의 공간은 10개이다. 그렇다면 부등호와 숫자를 같이 저장할 배열은 (부등호 * 2) + 1 개로 만든다면 부등호와 숫자를 모두 저장할 수 있다.

그 후 백트래킹을 돌면서 수를 하나씩 집어넣는다.
수를 집어 넣고 idx(집어 넣을 숫자)가 현재 배열의 길이보다 클 경우 숫자를 다 집어넣은 것이므로 isCorrect()로 넘어가 판단을 한다.

isCorrect 함수에서는 반복문을 돌면서 현재 탐색하는 문자가 부등호인지 아닌지를 먼저 판단한다.
만약 부등호라면 부등호 앞뒤의 수를 탐색한 부등호의 반대로 판단한다. 이유는 현재 탐색한 부등호의 반대로 판단했을 때 참이라면 false를 리턴하기 때문에 이는 올바른 부등호 관계가 아닌 것이다. 만약 배열의 끝까지 판단했을 때 조건문에 걸리지 않는다면 이는 올바른 부등호 관계이므로 true를 리턴하여 그 문자열의 부등호를 제거한 채 리스트에 넣는다.

이를 끝까지 반복한다면 부등호를 제거한 올바른 부등호 관계인 문자열들이 s_list에 저장된다.
그 후 이를 정렬하고 s_list.size() - 1번 인덱스의 값(리스트 값 중 가장 큰 값)과 0번 인덱스(리스트 값 중 가장 작은 값)의 값을 출력하면 정답!!!

 

3. 소스 코드 

import java.util.ArrayList;
import java.util.Collections;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static boolean[] visited;
    static int K;
    static List<String> s_list = new ArrayList<>();
    static String[] s_array;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        K = Integer.parseInt(br.readLine());
        s_array = new String[(2 * K) + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= K; i++) {
            s_array[(2 * i) - 1] = st.nextToken();
        }

        // 사용한 숫자를 표시하는 visited[]
        visited = new boolean[10];
        listBack(0);

        Collections.sort(s_list);
        bw.write(s_list.get(s_list.size() - 1) + "\n" +  s_list.get(0));
        bw.flush();
        bw.close();
        br.close();
    }

	// 백트래킹 탐색 함수
    private static void listBack(int idx) {
        if (idx > s_array.length) {
            if (isCorrect(s_array)) {
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < s_array.length; i++) {
                    sb.append(s_array[i]);
                }
                s_list.add(sb.toString().replaceAll(">", "").replaceAll("<", ""));
            }
            return;
        }

        for (int i = 0; i < 10; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            s_array[idx] = Integer.toString(i);

            listBack(idx + 2);
            visited[i] = false;
        }
    }

	// 올바른 부등호 관계인지 판별하는 함수
    private static boolean isCorrect(String[] s_array) {
        for (int i = 0; i < s_array.length; i++) {
            if (s_array[i].equals(">")) {
                if (Integer.parseInt(s_array[i - 1]) < Integer.parseInt(s_array[i + 1])) {
                    return false;
                }
            } else if (s_array[i].equals("<")) {
                if (Integer.parseInt(s_array[i - 1]) > Integer.parseInt(s_array[i + 1])) {
                    return false;
                }
            }
        }
        return true;
    }
}