[PS] 99클럽 코테 스터디 37일차 TIL (부등호)

문제

설명

부등호 기호들이 주어지고, 앞뒤에 0 ~ 9 의 숫자를 한번씩만 써서 모든 부등호를 만족하는 최대값, 최소값을 찾는 문제

풀이

• 입력 : 부등호 갯수가 k 이면 필요한 숫자는 k + 1
• 로직 :
  • 0 ~ 9 까지 차례대로 dfs 돌린다.
    • 이때 선택한 숫자는 재탐색 하지 않도록 visited 배열로 추적한다.
    • 현재 선택한 숫자는 arr 배열에 저장한다.
    • dfs 를 호출 시 depth 변수를 하나씩 늘리면서 현재 탐색 깊이를 관리한다.
  • depth == arr.length 조건 확인 :
    • depth 의 크기가 노드 간의 거리이며, arr.length 와 같으면 문제에서 요구하는 길이 조건을 만족한다. 이 경우 다시 상위 호출시점으로 되돌아가서 다음 항목을 탐색 한다. (백트래킹)
    • 최대 길이 도달 시 arr 에 담아 두었던 숫자가 부등호 조건에 만족하는지 검사한다. (isValid())
      • 조건 만족 시 result 에 담아둔다.
• 출력 : result 에 다음과 같이 들어가 있다.

  result = [021, 031, 032, 041, 042, 043, 051, 052, 053, 054, 061, 062, 063, 064, 065, 071, 072, 073, 074, 075, 076, 081, 082, 083, 084, 085, 086, 087, 091, 092, 093, 094, 095, 096, 097, 098, 120, 130, 132, 140, 142, 143, 150, 152, 153, 154, 160, 162, 163, 164, 165, 170, 172, 173, 174, 175, 176, 180, 182, 183, 184, 185, 186, 187, 190, 192, 193, 194, 195, 196, 197, 198, 230, 231, 240, 241, 243, 250, 251, 253, 254, 260, 261, 263, 264, 265, 270, 271, 273, 274, 275, 276, 280, 281, 283, 284, 285, 286, 287, 290, 291, 293, 294, 295, 296, 297, 298, 340, 341, 342, 350, 351, 352, 354, 360, 361, 362, 364, 365, 370, 371, 372, 374, 375, 376, 380, 381, 382, 384, 385, 386, 387, 390, 391, 392, 394, 395, 396, 397, 398, 450, 451, 452, 453, 460, 461, 462, 463, 465, 470, 471, 472, 473, 475, 476, 480, 481, 482, 483, 485, 486, 487, 490, 491, 492, 493, 495, 496, 497, 498, 560, 561, 562, 563, 564, 570, 571, 572, 573, 574, 576, 580, 581, 582, 583, 584, 586, 587, 590, 591, 592, 593, 594, 596, 597, 598, 670, 671, 672, 673, 674, 675, 680, 681, 682, 683, 684, 685, 687, 690, 691, 692, 693, 694, 695, 697, 698, 780, 781, 782, 783, 784, 785, 786, 790, 791, 792, 793, 794, 795, 796, 798, 890, 891, 892, 893, 894, 895, 896, 897]
  

• 맨 앞(최소값) 과 맨 뒤(최대값) 을 출력한다.

public class Main {
  static int[] arr;
  static boolean[] visited = new boolean[10];
  static String[] sign;
  static List<String> result = new ArrayList<>();

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int k = Integer.parseInt(br.readLine());

    sign = br.readLine().split(" ");
    arr = new int[k + 1];

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

  private static void dfs(int depth) {
    // 길이 도달 시 리턴
    if (depth == arr.length) {
      if (isValid()) {   // arr 의 항목이 부등호 조건을 만족하는지 검사
        StringBuilder sb = new StringBuilder();
        for (int num : arr) {
          sb.append(num);
        }
        result.add(sb.toString());
      }
      return;
    }
    
    // 0 ~ 9 까지 탐색한다
    for (int i = 0; i <= 9; i++) {
      if (!visited[i]) {
        visited[i] = true;   // 선택 숫자 방문처리
        arr[depth] = i;     // 선택 숫자 저장
        dfs(depth + 1);     // 조건 만족 시 다시 여기로 돌아온다
        visited[i] = false;    // 백트래킹 : 마지막 자리수를 다시 방문 할 수 있도록 false 로 만든다
      }
    }
  }

  // 부등호 조건에 맞지 않는 경우 제외시킨다
  private static boolean isValid() {
    for (int i = 0; i < sign.length; i++) {
      if (sign[i].equals("<")) {
        if (arr[i] >= arr[i + 1]) {
          return false;
        }
      } else if (sign[i].equals(">")) {
        if (arr[i] <= arr[i + 1]) {
          return false;
        }
      }
    }
    return true;
  }
}