Q 2529 부등호

💡 문제 요약 및 분석

두 종류의 부등호 ‘<’ ‘>’ 가 k개 나열된 순서열 A가 있다. 해당 부등호들 사이에 0~9의 정수를 넣어서 모든 부등호 관계를 만족시키려고 한다. 부등호 기호 앞뒤에 넣는 숫자는 모두 달라야 하며, 정답은 한 개 이상이다. 만약 아래와 같은 순서쌍을 만들었다고 했을 때, 순서쌍의 최댓값과 최솟값을 문자열로 출력하자.

A : < < < > < < > < >
#1. (최솟값) 3456128790
3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0
#2. (최댓값) 5689023174
5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

💡 알고리즘 설계

✅ 핵심 아이디어 : 모든 경우의 수를 탐색한다. 단, 부등호 조건에 맞지 않으면 시작 노드로 돌아가서 다시 탐색한다. (백트래킹)

1. 입력

   • 표준입력 : int K
   • 표준입력 : StringTokenizer로 K개의 부등호를 잘라서 배열로 저장해둔다.
   • boolean[] visit = {false, false, … false} 를 생성한다.
   • 가능한 모든 경우의 수를 List 에 저장한다.

2. 연산

   • 시작점 now 는 0부터 9까지 순차적으로 백트래킹 함수를 돌려 가능한 경우의 수를 모두 체크한다. 부등호 조건에 맞지 않으면 다시 시작점으로 돌린다.
   • 재귀함수 종료 시점 (count == K) 이다. 시작점은 정해져 있으니 재귀함수에서 나머지 K개의 숫자를 확인하면 종료된다.

3. 출력

   • 최댓값 : List 의 마지막 요소
   • 최솟값 : List 의 첫 번째 요소

💡 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int K;
    static char[] signs;
    static boolean[] visit = new boolean[10];
    static List<String> result = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        signs = new char[K];
        for (int i = 0; i < K; i++) {
            signs[i] = st.nextToken().charAt(0);
        }

        for (int i = 0; i < 10; i++) {
            visit[i] = true;
            backTracking(i, 0, i+"");
            visit[i] = false;
        }

        System.out.println(result.get(result.size() - 1));
        System.out.println(result.get(0));
    }

    static void backTracking(int now, int count, String number) {
        if (count == K) {
            result.add(number);
            return;
        }

        for (int next = 0; next < 10; next++) {
            if (visit[next] == false) {
                if ((signs[count] == '<' && now < next) || (signs[count] == '>' && now > next)) {
                    visit[next] = true;
                    backTracking(next, count + 1, number + next);
                    visit[next] = false;
                }
            }
        }
    }

}