[Baekjoon] 2992_크면서 작은 수

Silver III

문제(출처: https://www.acmicpc.net/problem/2992)

---

< 크면서 작은 수 >

 

문제 풀이 

 

X보다 큰 수 중 가장 작은 수를 구하기 위해 X를 구성하는 수를 배열에 저장하여 정렬한다.

정렬한 배열을 조합론을 사용하여 구한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class _2992_ { // 크면서 작은 수
	static int temp[], result[];
	static boolean visited[], flag;
	static String str, answer;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		str = bf.readLine();

		temp = new int[str.length()];
		result = new int[str.length()];
		visited = new boolean[str.length()];
		flag = false;

		for (int i = 0; i < str.length(); i++) {
			temp[i] = str.charAt(i) - '0';
		}

		Arrays.sort(temp);

		search(0);

		if (!flag)
			System.out.println(0);
	}

	private static void search(int idx) {
		if (idx == result.length) {
			answer="";
			for (int i = 0; i < result.length; i++) {
				answer += Integer.toString(result[i]);
			}

			if (!flag && Integer.parseInt(answer) > Integer.parseInt(str)) {
				flag = true;
				System.out.println(answer);
			}

			return;
		}

		for (int i = 0; i < temp.length; i++) {
			if (!visited[i]) {
				visited[i] = true;
				result[idx] = temp[i];
				search(idx + 1);
				visited[i] = false;
				if (flag)
					return;
			}
		}
	}
}

 

Main

변수)
str : 정수 X
temp : 정수 X를 구성하는 숫자
result : 결과 저장 배열
visited : 방문 여부
flag : 정답 여부

 

- 정수 X(str) 입력

- 정수 X를 구성하는 숫자를 배열 temp에 저장 후 오름차순 정렬

- search 함수 호출

- 정수 X보다 큰 수 중 가장 작은 수를 만들 수 없다면 0 출력

 

Search

- X와 구성이 같은 수를 구했다면 아직 정답을 찾지 못했고 그 수가 정수 X보다 큰 수라면 답이므로 정답 출력

- temp 배열을 순환하며 아직 방문하지 않은 수라면 방문 표시 및 result 배열에 저장 후 다시 search 함수 호출. 함수 호출 후 다음 조합을 위해 방문 표시를 해제 (만약 flag가 true라면 이미 답을 구해서 다음 조합을 구할 필요가 없으므로 return)

---

---