728x90
문제
두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다.
가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.
입력
첫째 줄에 두 정수 A와 B가 주어진다.
출력
B보다 작은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.
제한
- 1 ≤ A, B < 109
풀이 방법
A 숫자의 배치를 바꿈으로써, B에 가장 근접한 수를 찾기 위해서 A를 순열로써 탐색을 해야한다.
또한, 완성된 숫자의 첫번째 값이 0이여서는 안되고, B보다는 작아야 되므로 추가적인 조건이 필요하다.
작성 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
package baekjoon.bruteforcing;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ_16943 {
static int max=-1;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
int A=Integer.parseInt(st.nextToken());
int B=Integer.parseInt(st.nextToken());
String s = String.valueOf(A);
char arr[]=new char[s.length()];
for(int i=0;i<s.length();i++){
arr[i]=s.charAt(i); // 순열을 위한 정수 쪼개기 작업
}
permutation(arr,0,arr.length,B);
System.out.println(max);
}
public static void permutation(char arr[], int index, int r, int B){
if(index==r){
if(arr[0]!='0')
check(arr,r,B);
return;
}
for(int i=index;i<arr.length;i++){
swap(arr,index,i);
permutation(arr,index+1,arr.length,B);
swap(arr,index,i);
}
}
public static void swap(char arr[], int index, int i){
char temp=arr[index];
arr[index]=arr[i];
arr[i]=temp;
}
public static void check(char arr[], int r, int B){
String result="";
for(int i=0;i<r;i++){
result+=arr[i];
}
int value = Integer.parseInt(result);
if(value<B){
max=Math.max(max,value);
}
}
}
|
다른 방법
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
package baekjoon.bruteforcing;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ_16943 {
static int A,B;
static int arr[];
static boolean visited[];
static int max = -1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
String s = String.valueOf(A);
arr = new int[s.length()];
visited=new boolean[s.length()];
for (int i = 0; i < s.length(); i++) {
arr[i] = s.charAt(i)-'0'; // 순열을 위한 정수 쪼개기 작업
}
permutation(0,0,arr.length);
System.out.println(max);
}
public static void permutation(int value, int depth, int r){
if(depth==r){
max=Math.max(max,value);
return;
}
for(int i=0;i<arr.length;i++){
if(visited[i] || (depth==0 && arr[i]==0)) continue;
if(value*10+arr[i]>B) continue;
visited[i]=true;
permutation(value*10+arr[i],depth+1,r);
visited[i]=false;
}
}
}
|
- 순열로 탐색할 때, swap()이 아닌 visited[]로써 탐색을 하였고,
처음에 값을 char형이 아닌 int형으로써 설정하여 자리수가 증가할 때는 value*10으로써 표현해주었다.
또한, 순열의 함수 과정에서 0인 경우와 범위를 벗어나는 경우를 미리 탐색하는 과정을 거쳤다.
- 수행 시간은 2번째 풀이가 더 빠르게 나타났다.
728x90
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 2980번 : 도로와 신호등 (0) | 2022.02.02 |
|---|---|
| [백준] 3048번 : 개미 (0) | 2022.02.02 |
| [백준] 8979번 : 올림픽 (0) | 2022.01.26 |
| [백준] 1476번 : 날짜 계산 (0) | 2021.12.22 |
| [백준] 1182번 : 부분수열의 합 (0) | 2021.12.21 |
