[ 백준 / BOJ 16943 ] 숫자 재배치 ( 자바 / JAVA )

[ 백준 / BOJ 16943 ] 숫자 재배치 ( 자바 / JAVA )

728x90

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

문제

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다.

가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

B보다 작은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.

풀이

DFS를 이용

DFS 로 A를 다양한 수로 조합하고 모두 사용했다면 B와 비교 후, 작은 값이면 기존의 값과 더 큰 값을 선택 ‼️

코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main_BOJ_16943_숫자재배치 { static String A, B, C; static int a,b,c; static boolean[] isVisited; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer stringTokenizer = new StringTokenizer(br.readLine()); A = stringTokenizer.nextToken(); B = stringTokenizer.nextToken(); C = ""; a = Integer.parseInt(A); b = Integer.parseInt(B); c = -1; isVisited = new boolean[A.length()]; DFS(); System.out.println(c); } private static void DFS() { if(C.length() == A.length()){ if(Integer.parseInt(C) < b) c = Math.max(c, Integer.parseInt(C)); return; } for(int i = 0 ; i < A.length(); i++){ if((C.length() == 0 && A.charAt(i) == '0') || isVisited[i]) continue; isVisited[i] = true; C += A.charAt(i); DFS(); isVisited[i] = false; C = C.substring(0, C.length()-1); } } }

728x90

from http://hyeyun.tistory.com/81 by ccl(A) rewrite - 2021-10-28 22:01:34