99클럽 코테 스터디 13일차 TIL - 백트래킹

문제 💁🏻‍♂️

문제 링크 - 백준 2529 부등호

해결 과정

문제를 보고 느낀 점은 "어떻게 접근해야하지?" 였다. 각 부등호에 맞는 숫자들을 어떻게 끼워넣어야 할까? 에 대해서 곰곰히 생각해 보았다.

사고 과정 ❗️

k의 범위를 보자. k의 범위가 2 ≤ k ≤ 9 라는 점을 파악했다. 우선, 문제를 이해하고 완전 탐색 풀이법으로 접근을 해보려고 했다. 완전 탐색으로 문제를 접근하려고 보니 결국 0부터 9까지의 10개의 숫자를 최대 10자리에 넣는 모든 순열의 수는 10! = 3_628_800 으로 충분히 문제를 풀이할 수 있는 시간복잡도이다.

완전 탐색으로 문제를 풀이할 수 있음을 알고 나서는 최적화에 들어갔다. 시간복잡도를 어떻게 하면 더 줄일 수 있을까? 그것은 바로. 유망하지 않다고 판단되면 탐색을 멈추는 백트래킹 기법이 떠올랐다. 유망함을 판단하는 기준은 다음과 같이 설정했다.

1. 주어지는 부등호가 '<'인데, arr[i] > arr[i + 1] 라면, 탐색하지 않는다.
2. 주어지는 부등호가 '>'인데, arr[i] < arr[i + 1] 라면, 탐색하지 않는다.
3. 이 과정을 모두 만족하여 List 크기가 k + 1이라면, MAX, MIN 크기 비교를 통해 값을 갱신한다.

위 3가지 과정을 중점적으로 백트래킹 코드를 풀어나갔다. 더불어, 중복되는 숫자를 포함하지 않도록 visited 배열을 사용하여 방문 처리를 해줬고, 방문 처리와 복원 처리를 하며 배열을 효과적으로 활용했다. 많은 시간을 들여 고민했고, 고민한 내용을 바탕으로 코드로 옮겼다. 최적화를 하기 위해서 많은 시간을 할애했지만, 한번에 문제를 통과할 수 있어서 좋은 시간이라고 생각한다.

코드

정답 코드

import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int k;
    static long MAX, MIN;
    static char[] arr;
    static ArrayList<Integer> lst;
    static boolean[] visited;
    static String str, SMAX, SMIN;

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

        input();

        solve();

    }

    private static void solve() {

        MAX = -1;
        MIN = Long.MAX_VALUE;
        for (int i = 0; i < 10; i++) {
            lst = new ArrayList<>();

            lst.add(i);
            visited[i] = true; // 시작점 방문 처리
            bt(1, lst);
            visited[i] = false; // 시작점 복원 처리
        }

        System.out.println(SMAX);
        System.out.println(SMIN);

    }

    private static void bt(int cnt, ArrayList<Integer> lst) {

        // k + 1 개의 숫자를 모두 채웠다면 -> 저장
        if (cnt == k + 1) {

            for (Integer num : lst)
                sb.append(num);

            str = sb.toString();
            if (MAX < Long.parseLong(str)) {
                MAX = Long.parseLong(str);
                SMAX = str;
            }

            if (MIN > Long.parseLong(str)) {
                MIN = Long.parseLong(str);
                SMIN = str;
            }

            sb.setLength(0); // 초기화
            return;
        }

        for (int i = 0; i < 10; i++) {

            if (arr[cnt - 1] == '<' && lst.get(lst.size() - 1) > i)
                continue;
            if (arr[cnt - 1] == '>' && lst.get(lst.size() - 1) < i)
                continue;

            // 방문한 적이 없는 경우 -> 탐색
            if (!visited[i]) {
                visited[i] = true; // 방문 처리
                lst.add(i);
                bt(cnt + 1, lst);
                lst.remove(lst.size() - 1);
                visited[i] = false; // 복원 처리
            }
        }

    }

    private static void input() throws IOException {

        // 입력 부분
        k = Integer.parseInt(br.readLine());
        visited = new boolean[10];

        arr = new char[k];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < k; i++)
            arr[i] = st.nextToken().charAt(0);

        br.close();
    }
}

Reference

• 내 머릿 속