BEAKJOON / 백준 - JAVA 18511번 큰 수 구성하기

2024.08.12기준 - 실버5

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 수 n과 1 ~ 9까지의 숫자들이 주어졌을 때, 1 ~ 9 까지 주어진 수를 이용해 n보다 작거나 같은 수 중 제일 큰 값을 출력하는 문제입니다.

 

1. 이 문제는 재귀함수를 통해 풀어나갔습니다.

private static void function(int num) {
    if (num > n) { // 값이 더 커지면 멈춘다.
        return;
    }

    if (max < num) { // 현재 max값 보다 num이 더 크면 max값을 변경
        max = num;
    }

    // 모든 수를 다시 재귀
    for (int i = k - 1; i >= 0; i--) {
        function(num * 10 + arr[i]);
    }
}

 

모든 수를 일의 자리에 추가를 해주면서 주어진 수가 n보다 커지면 break를 크지 않고,

현재 max값 보다 크다면 max값에 저장을 한 뒤 다시 일의 자리에 수를 추가해줍니다.

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	static int[] arr;
	static int n, k, max = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 최대 수
		k = Integer.parseInt(st.nextToken()); // 원소의 개수
		
		arr = new int[k];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < k; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// 오름차순 정렬
		Arrays.sort(arr);
		function(0);
		
		bw.write(Integer.toString(max));
		bw.flush();
		bw.close();
		br.close();
	}
	
	private static void function(int num) {
		if (num > n) { // 값이 더 커지면 멈춘다.
			return;
		}
		
		if (max < num) { // 현재 max값 보다 num이 더 크면 max값을 변경
			max = num;
		}
		
		// 모든 수를 다시 재귀
		for (int i = k - 1; i >= 0; i--) {
			function(num * 10 + arr[i]);
		}
	}
}