[백준] 2529번 부등호 문제 풀이방법!! (Java로 순열 구현하기)
1. 문제
1) 링크
2) 문제
두 종류의 부등호 기호 ‘<’와 ‘>’가 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 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.
3) 입력
첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다.
4) 출력
여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.
더 자세한 문제의 조건을 알아보기 위해서는 위의 링크에 들어가보자.
2. 풀이
이 문제는 순열을 사용하여서 가능한 경우의 수를 체크해봐야 한다.
원래같으면 k개의 부등호가 있고 k+1개의 숫자를 10개중에서 택해야겠지만 이 문제의 경우 가장 큰수와 가장 작은 수를 구하는 것이기 때문에 굳이 랜덤으로 택하지 않아도 되는 것이 핵심인 문제이다.
예를 들어 부등호가 2개이면 3개의 수를 골라야 하기 때문에 가장 큰 수는 9,8,7을 조합해서 부등호를 만족시키는 것 중 가장 큰 수, 가장 작은 수는 0,1,2를 조합해서 부등호를 만족시키는 것 중 가장 작은 수를 택하면 되는 것이다.
C++의 경우에는 next_permutation이라는 것이 존재하여 순열의 다음 항을 바로 쉽게 찾을 수 있는 반면, java의 경우 순열의 다음 항을 바로 찾을 수 있는 내장 메서드가 없다. 따라서 자신이 직접 구현을 해주어야 하는데
이 문제의 경우 가장 큰 수의 경우 가장 큰 수부터 작아지는 식으로 탐색을 해야 하고, 가장 작은 수의 경우 가장 작은 수부터 커지는 순서로 탐색을 진행해야 하기 때문에 두가지의 함수를 만들기로 했다.
public static boolean next_permutation(int[] small){
int i=small.length-1;
while(i>0 && small[i-1]>=small[i]) {
//내림차순의 시작점 찾기
i--;
}
if (i<=0) return false; //가장 큰 값이므로 다음것이 없음
int j=small.length-1;
while(small[j]<=small[i-1]){ //더 큰것으로 바꾸어주어야 하므로 작으면 계속 조정
j--;
}
int tmp=small[i-1];
small[i-1]=small[j];
small[j]=tmp;
j=small.length-1;
while(i<j){
tmp=small[i];
small[i]=small[j];
small[j]=tmp;
i++;
j--;
}
return true;
}
위의 소스는 지금 수보다 큰 다음순열의 수를 찾기 위한 코드이다. 주석으로 해당 코드가 무엇을 의미하는지 적었기 때문에 쉽게 이해할 수 있을 것이다. 먼저 내림차순의 시작점을 찾고 그 전의 숫자와 그보다 큰 숫자를 바꾼다. 이후 그 사이의 숫자들을 정렬해주는 과정을 거친다. 위의 코드만 이해한다면 지금 수보다 작은 다음순열의 수를 찾기 위한 코드는 부등호만 바꿈으로써 쉽게 작성할 수 있다.
public static boolean prev_permutation(int[] big){
int i=big.length-1;
while(i>0 && big[i-1]<=big[i]) {
//오름차순의 시작점 찾기
i--;
}
if (i<=0) return false; //가장 작은 값이므로 다음것이 없음
int j=big.length-1;
while(big[j]>=big[i-1]){ //더 작은것으로 바꾸어주어야 하므로 크면 계속 조정
j--;
}
int tmp=big[i-1];
big[i-1]=big[j];
big[j]=tmp;
j=big.length-1;
while(i<j){
tmp=big[i];
big[i]=big[j];
big[j]=tmp;
i++;
j--;
}
return true;
}위의 코드는 현재 수보다 작은 다음수의 순열을 찾기 위한 코드이다. 보면 전의 코드와 크게 다른 점이 없다는 것을 알 수 있다.
이런식으로 두 가지의 함수 배열을 준비해놓고 두 개의 배열을 준비해놓는다.
small 이라는 배열과 big이라는 배열을 준비해서 small 배열에는 0부터 작은 숫자들 k+1개, big 배열에는 9부터 큰 숫자들 k+1개를 넣어놓는다. 그리고 이것을 순열로 조합하여서 부등호를 만족시키는지 보는 것이다.
부등호를 만족시키는지 보는 방법은 check라는 함수를 만들어서
public static boolean check(int[] arr, char[] comp){
for(int i=0; i<comp.length; i++){
if (comp[i]=='<' && arr[i]>arr[i+1]){
return false;
}
if (comp[i]=='>' && arr[i]<arr[i+1]){
return false;
}
}
return true;
}부등호 관계를 만족시키는지 아닌지를 true/false로 return해주는 식인 것이다.
이런식으로 전체 코드를 살펴보면,
import java.util.*;
public class Main{
static int [] small;
static int[] big;
public static boolean check(int[] arr, char[] comp){
for(int i=0; i<comp.length; i++){
if (comp[i]=='<' && arr[i]>arr[i+1]){
return false;
}
if (comp[i]=='>' && arr[i]<arr[i+1]){
return false;
}
}
return true;
}
public static boolean next_permutation(int[] small){
int i=small.length-1;
while(i>0 && small[i-1]>=small[i]) {
//내림차순의 시작점 찾기
i--;
}
if (i<=0) return false; //가장 큰 값이므로 다음것이 없음
int j=small.length-1;
while(small[j]<=small[i-1]){ //더 큰것으로 바꾸어주어야 하므로 작으면 계속 조정
j--;
}
int tmp=small[i-1];
small[i-1]=small[j];
small[j]=tmp;
j=small.length-1;
while(i<j){
tmp=small[i];
small[i]=small[j];
small[j]=tmp;
i++;
j--;
}
return true;
}
public static boolean prev_permutation(int[] big){
int i=big.length-1;
while(i>0 && big[i-1]<=big[i]) {
//오름차순의 시작점 찾기
i--;
}
if (i<=0) return false; //가장 작은 값이므로 다음것이 없음
int j=big.length-1;
while(big[j]>=big[i-1]){ //더 작은것으로 바꾸어주어야 하므로 크면 계속 조정
j--;
}
int tmp=big[i-1];
big[i-1]=big[j];
big[j]=tmp;
j=big.length-1;
while(i<j){
tmp=big[i];
big[i]=big[j];
big[j]=tmp;
i++;
j--;
}
return true;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
char[] a=new char[n];
for(int i=0; i<n; i++){
a[i]=sc.next().charAt(0);
}
small=new int[n+1];
big=new int[n+1];
for(int i=0; i<=n; i++){
small[i]=i;
big[i]=9-i;
}
do { //가장 큰 수 찾기
if (check(big, a)) {
break;
}
} while(prev_permutation(big));
do { //가장 작은 수 찾기
if (check(small, a)) {
break;
}
} while(next_permutation(small));
for (int i=0; i<big.length; i++) {
System.out.print(big[i]);
}
System.out.println();
for (int i=0; i<small.length; i++) {
System.out.print(small[i]);
}
System.out.println();
}
}위와 같다. 여기서 while 문이 아니라 do-while문을 사용한 이유는 가장 처음의 숫자 배열이 정답일수도 있기 때문에 무작정 다음 배열의 조합을 구하지 않기 위함이다. 이렇게 하면 쉽고 간단하게 구할 수 있다.
만약 함수를 구현하기 싫다면 C++를 사용하면 된다. C++에서는 next_permutation이라는 것을 사용하면 우리가 함수를 구현하지 않고도 바로 다음 순열의 수를 알 수 있다. 다만 Java에서는 해당 기능이 없기 때문에 우리가 직접 구현해주어야 한다.