문제 탐색하기

입력 자료 정리하기

1. 처음 주어지는 k는 이후 주어질 부등호 문자의 개수이다
2. 주어지는 부등호는 k개만큼 주어지며, 이후 탐색과정의 조건으로 사용된다

해결방법 추론

1. 먼저 비교가 될 숫자는 0~9이므로 부등호마다 0부터 9까지의 수를 다 넣어보며, 조건에 해당되도록 만들면 될 것이다.
2. 방식에 있어서는 고민을 해야하는데,
   만약 가능한 경우가 단 한가지로만 고정되어 있다면 브루트 포스로 쉽게 구현할 수 있었을 것이다
3. 하지만 이 방식은 여러가지 경우가 나올 수도 있기 때문에 브루트포스 방법은 무리가 있고,
   따라서 백트래킹을 사용하면 쉽게 해결할 수 있겠다고 생각하였다
4. 이때 비교해야하는 부등호의 개수는 k개지만, 비교해야하는 수는 k+1개이다
5. 따라서 시작 숫자에 대해서는 브루트포스로 0~9까지 다 넣어가면서
   선택하는 방법이 필요하다 생각하였고 이후 탐색은 백트래킹을 활용하면 될 것이라고 생각하였다
6. 저번 문제처럼 이 문제도 브루트포스와 백트래킹을 활용하여 해결하는 문제다
7. 하지만 역시 브루트포스와 백트래킹은 시간제한을 고민해야한다.

시간복잡도 계산

1. 시간 제한은 1초이므로 연산이 1억을 넘기면 안된다
2. 먼저 브루트포스를 하는 경우는 시작 지점을 0부터 9까지 선택하는 경우이므로
   10의 경우의 수가 나온다
3. 이어서 백트래킹 하는 경우를 생각해보면 k번 만큼 10번의 순회를 돌아야 한다.
4. 이때 k의 최대 수는 9이므로 9^10이라는 시간복잡도가 발생한다
5. 브루트포스하면서 백트래킹을 진행하므로 둘의 시간복잡도는 곱연산이 된다
6. 따라서 O(10 X 9^10)라는 시간복잡도가 발생한다
7. 그런데 이 시간복잡도에 따르면 100억이 넘는 연산이 발생한다.
8. 시간제한에 걸려서 해당 방법으로는 해결할 수 없을 것으로 보인다

방법 선택 고민

1. 단순히 백트래킹과 브루트포스를 사용하니 시간제한에 걸리는 문제가 발생하였다.
2. 그렇다면 두 방법으로는 이 문제를 해결할 수 없고 다른 방법을 선택해야하는 것일까?
3. 다른 방법을 고민하면서 다시 문제를 읽어봤고, 위 시간복잡도 계산이 틀린 것을 알게 되었다
4. 이 문제에서는 선택된 숫자는 모두 달라야 한다는 조건이 있다!

시간복잡도 다시 계산

1. 위 조건을 위해 방문 체크를 하는 boolean 배열을 설계하였다.
2. 즉 백트래킹 과정 속에서 이미 선택된 숫자는 이후 연결되는 문자에서 다시 선택되면 안된다!
3. 따라서 시간복잡도는 다음과 같이 줄어들게 된다
4. 브루트포스에서는 10가지 경우 모두, 이후부터는 9 -> 8 -> 7 -> 6... -> 1로 선택 경우가 줄어든다
5. 이 모습을 보았을 때, 팩토리얼을 떠올릴 수 있고
   나올 수 있는 시간복잡도는 O(10!)이라는 것을 알게 되었다
6. O(10!)은 360만 정도로 시간제한에 걸리지 않는다!
7. 따라서 브루트포스와 백트래킹, 그리고 방문배열을 활용한다면 해당 방법으로 해결할 수 있다!

코드 설계하기

입력값 상태 관리

1. k는 int형 변수로 받아 관리하며, 부등호는 char 타입의 배열로 받아 관리한다

탐색결과 상태를 관리할 자료구조 선택

1. 백트래킹 결과 나오는 경우의 수는 여러가지가 될 수 있다.
2. 또한 최댓값과 최솟값을 구해야하기 때문에 백트래킹 결과를 보존할 자료구조가 필요하다
3. 처음에는 선택된 숫자는 모두 달라야 한다는 조건 때문에 Set을 선택하였다
4. 하지만 Set은 정렬하기도 복잡하고,
   방문 배열때문에 중복 제거를 목적으로 이 자료구조를 선택할 필요가 없다는 것을 알게 되었다
5. 방문 배열로 이미 선택된 문자는 다시 선택하지 않기 때문에 중복 문자는 발생하지 않는다
6. 그래서 Set이 아닌 확장과 정렬이 자유로운 List를 상태 관리 자료구조로 선택하였다

탐색 로직 설계

방문배열 설계

1. boolean 타입의 배열로 선언하였다
2. backtracking 전에는 탐색 체크를 위해 true, 종료 후에는 false로 체크를 지워준다

브루트포스 설계

1. 0부터 9까지의 수를 시작으로 선택하도록 순회를 돌면서 backtracking함수를 실행하도록 설계하였다
2. 이때 매 실행 전에 방문 배열 초기화를 진행하고, 시작값에 대한 방문 체크를 한다
3. 매 순회마다 방문 배열을 초기화하므로 브루트포스 순회에서는
   backtracking 종료후에 방문 배열 체크를 지워줄 필요가 없다.

backtracking 함수식

- void backtracking(int depth, int k, String s)
1. depth는 현재 비교하려는 부등호를 의미하면서도 종료의 조건이 된다
2. k는 재귀 함수의 base condition 활용을 위해 파라미터로 설정하였다
3. s에는 선택된 숫자가 누적되어 있다. 이 값을 바탕으로 현재와 이전값을 비교한다

재귀식

- backtracking(depth+1, k, s + i)
1. 종료를 위해 depth는 값을 증가시켜주며, k는 종료를 위해 고정되어 있어야 하므로 그대로 넘겨준다
2. s에다가 현재 탐색하는 숫자인 i를 넣어준다

base condition

- if(depth == k) {...}
1. 종료조건은 depth랑 k가 같을 때이다.
2. 이때 list에 완성된 s를 넣어준다

backtracking 탐색에 대한 설계

1. backtracking 과정에서도 0~9까지 순회하면서 조건에 해당되는지 비교한다
2. 먼저 방문을 했는지 체크한다. 방문했으면 continue해준다
3. 방문 체크여부를 통과하면 이전 값을 가져온다
4. 이전 값은 누적된 문자열인 s의 depth번째 문자다.
5. 이 문자를 파싱해서 int타입으로 last 변수에 가져온다
6. backtracking 재귀식 실행을 위한 조건을 만족해야한다. 이 조건은 문제에서 주어진 다음 조건이다
7. 앞서 불러온 last 변수의 값과 현재 i를 비교하는데,
   이 비교식이 arr[depth]에 있는 부등호를 넣었을 때 참인지를 비교한다
8. '>'일때나 '<'일때 각각의 조건을 만족한다면 재귀식을 실행한다
9. 이때 앞서 말한 방문배열 설계에서 말한
   백트래킹 전 방문 체크와 종료 후 방문 체크 제거를 반드시 진행해주어야한다!

정답 조건 고민

1. 위 탐색과정을 통해 가능한 모든 경우를 list에 담아 왔다
2. 이제 정답으로 출력해야하는 수를 확인해보자
3. 최댓값과 최솟값이다. 문자열타입으로 list에 저장했으니, 사전 순으로 정렬한 뒤 출력해도 될것이다
4. 하지만 추가 정렬을 할 필요는 없다. 어차피 탐색을 0부터 9까지 순차적으로 진행했기 때문이다!
5. 따라서 제일 먼저 들어오는 값이 최솟값이고 제일 나중에 들어오는 값은 최댓값이다

출력 설계

1. 최댓값은 list.size()-1번째 인덱스에 있는 값을 출력해주면 된다
2. 최솟값은 0번째 인덱스에 있는 값을 출력해주면 정답이 된다.

정답코드

(1회 시도 성공!)

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

public class Main {

    static char[] arr;
    static boolean[] visited;
    static List<String> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int k = Integer.parseInt(br.readLine());
         arr = new char[k];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            arr[i] = st.nextToken().charAt(0);
        }

        for (int i = 0; i < 10; i++) {
            visited = new boolean[10];
            visited[i] = true;
            backtracking(0, k, String.valueOf(i));
        }

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

        br.close();
        bw.close();
    }

    private static void backtracking(int depth, int k, String s) {
        if(depth == k){
            list.add(s);
            return;
        }
        for (int i = 0; i < 10; i++) {
            if(visited[i]){
               continue;
            }
            int last = Character.getNumericValue(s.charAt(depth));
            if((arr[depth] == '>' && last > i) || (arr[depth] == '<' && last < i)){
                visited[i] = true;
                backtracking(depth+1, k, s + i);
                visited[i] = false;
            }
        }
    }

}

해결 핵심 키워드

• 브루트포스
• 백트래킹
• 파싱
• 자료구조 선택
• 방문 배열

문제 링크

2529번 - 부등호