BOJ 2529
위 문제는 백준 사이트의 알고리즘 2529 문제에 관한 설명입니다.
BOJ 2529
부등호
두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다.
우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다.
예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.
A => < < < > < < > < >
부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다.
아래는 부등호 순서열 A를 만족시키는 한 예이다.
3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0
이 상황에서 부등호 기호를 제거한 뒤,
숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다.
그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다.
예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다.
5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4
여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다.
앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.
입력
첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다.
그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다.
k의 범위는 2 ≤ k ≤ 9 이다.
출력
여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다.
단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다.
모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.
package Greedy;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
class Main {
static boolean[] visited = new boolean[10];
static String[] array = new String[10];// K의 범위는 2~9
static ArrayList<String> list = new ArrayList<String>();
static int k;
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());
for (int i = 0; i < k; i++) {
array[i] = st.nextToken();
}
for (int i = 0; i <= 9; i++) {
visited[i] = true;
dfs(0, i, i + "");
}
// for(String x: list)
// System.out.println(x);
System.out.println(list.get(list.size() - 1));
System.out.println(list.get(0));
}
private static void dfs(int count, int index, String str) {
if (count == k) {
list.add(str);
visited[index] = false;
return;
}
for (int i = 0; i < 10; i++) {
if (visited[i])
continue;
if (index == i)
continue;
if (array[count].equals(">")) {
if (index < i)
continue;
} else if (array[count].equals("<")) {
if (index > i)
continue;
}
visited[i] = true;
dfs(count + 1, i, str + i);
}
visited[index] = false;
}
}
그리디 알고리즘 문제를 풀었습니다.
이번 문제는 순열을 이용해서 풀었습니다.
순열이란?
n 개의 값 중에서 r 개의 숫자를 모든 순서대로 뽑는 경우를 말합니다.
DFS를 돌면서 모든 인덱스를 방문하여 원하는 결과(result)를 얻도록 String이든 배열이든 다양한 방식으로 값을 넣어줍시다.
이미 들어간 값은 visited 값을 true 로 바꾸어 중복하여 넣지 않도록 합니다.
count 즉, 깊이의 크기가 원하는 k 만큼 되면 result 에 들어있는 값을 출력하면 됩니다.
그래서 이번 문제는?
dfs를 활용해서 풀수 있었고, 여기에 추가적으로 해야한 것은 부등호에 따라 그것보다 작은 값이면 또는 큰값이면
continue를 통해 생략하는 과정이 필요했습니다.
이후 모든 조건이 만족하는 값들을 list에 넣어줍니다.
main에서 index가 0부터 늘어나므로 먼저들어가는 값들은 자동적으로 작은 값이 됩니다.
따라서 list의 첫번째, 그리고 마지막 값은 가장 작은값과 가장 큰 값입니다.