[JAVA] #2529 부등호

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

2529번: 부등호

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int N;
    static int cnt = 0;
    static String min, max;
    static char[] arr = new char[10];
    static int[] nums;
    static boolean[] visited = new boolean[10];

    public static void func(int depth) {
        if(depth == N + 1) { // 부등호의 개수가 N개이므로 depth는 N + 1까지 내려가야함
            if(cnt == 0) { // 제일 처음 나온 배열이 최솟값이 됨으로 String min에 저장
                min = Arrays.toString(nums);
            }
            cnt++;
            max = Arrays.toString(nums); // 제일 마지막에 나온 배열이 최댓값이 됨으로 Sting max에 저장
            return;
        }
        for(int i = 0; i <= 9; i++) { // 백트래킹
            if(!visited[i]) {
                if(depth > 0 && arr[depth - 1] == '<') { // 부등호에 따른 조건 체크
                    if(nums[depth - 1] > i) {
                        continue;
                    }
                } else if (depth > 0 && arr[depth - 1] == '>') { // 더 깔끔한 방법이 있을 것 같긴 한데 모르겠다
                    if(nums[depth - 1] < i) {
                        continue;
                    }
                 }
                visited[i] = true;
                nums[depth] = i;
                func(depth + 1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {

        // 입력
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        nums = new int[N + 1];
        for(int i = 0; i < N; i++) {
            arr[i] = sc.next().charAt(0);
        }

        // 메인
        func(0);

        // 출력
        String[] output = max.replace("[", "").replace("]", "").split(", ");
        for (String s : output) {
            System.out.printf("%s", s);
        }
        System.out.println();
        output = min.replace("[", "").replace("]", "").split(", ");
        for (String s : output) {
            System.out.printf("%s", s);
        }
    }
}

정보 올림피아드 "초등부" 문제

초등학생이 이런 문제를 풀어내다니 대한민국의 미래가 밝을 것임에 틀림없다.

 

처음에 어떻게 풀어야하나 고민을 좀 했었는데

반복문 -> 재귀 -> 백트래킹 의식의 흐름으로 백트래킹으로 풀어보았더니 정답이 나왔다 

괜히 문제를 많이 풀어봐야 한다는게 아니었다. 눈에 구조가 대충 익으니까 코드가 슬슬 짜진다

완전탐색 문제의 경우에는 백트래킹 기법을 꼭 생각해보자!

 

 

최소, 최댓값 배열을 저장해서 이쁘게 숫자로 출력하는 좀더 깔쌈한 방법이 있을법도 한데 마땅히 생각이 안나서 그냥 너저분한 반복문을 찍었다.

 

아무튼.. 해결!