[백준] PS/Java [실랜디]
[백준 2529] 부등호 - JAVA
SH3542
2025. 5. 4. 02:15
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;
}
}
}
}