[백준 2529] 부등호 - JAVA

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

 

부등호 조건을 만족하는 수열의 최대/최소값을 찾는 문제

 

1. 구성요소 외에 순서가 고려 대상이고, 최대 최소를 모두 구해야하므로 완전탐색해야 함

2. 수열을 0-9 순서로 뽑기 때문에 정렬은 필요 없음

 

나는 검증 후 재귀하는 방식으로 구현했다.

수열을 일단 전부 뽑아놓고 검증하는게 구현은 좀 더 쉬울 것 같다. 그래도 10!으로 널널하다.

 

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

class Main {

  static int N;
  static boolean[] b, vst = new boolean[10];
  static List<String> l = new ArrayList<>();

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    b = new boolean[N];

    StringTokenizer st = new StringTokenizer(br.readLine());

    for (int i = 0; i < N; i++) {
      b[i] = ">".equals(st.nextToken());
    }

    for (int i = 0; i < 10; i++) {
      vst[i] = true;
      solve(0, String.valueOf(i));
      vst[i] = false;
    }

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

  static void solve(int d, String s) {

    if (d == N) {
      l.add(s);
      return;
    }

    int tail = s.charAt(s.length() - 1) - '0';
    for (int i = 0; i < 10; i++) {
      if (!vst[i] && ((b[d] && tail > i) || (!b[d] && tail < i))) {
        vst[i] = true;
        solve(d + 1, s + String.valueOf(i));
        vst[i] = false;
      }
    }
  }
}