[Baekjoon] 16943_숫자 재배치

Silver I

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

---

< 숫자 재배치 >

 

문제 풀이 

 

b보다 작은 값 중에서 가장 큰 값을 구하기 위해 a를 구성하는 숫자를 배열에 저장해 내림차순으로 정렬한다.

정렬 후 조합을 통해 값을 구한다.

 

 my solution (Java)

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

public class _16943_ { // 숫자 재배치
	static Integer temp[];
	static int result[], b;
	static boolean flag, visited[];

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

		String a = st.nextToken();
		b = Integer.parseInt(st.nextToken());

		if (a.length() > Integer.toString(b).length())
			System.out.println(-1);
		else {
			temp = new Integer[a.length()];
			result = new int[a.length()];
			visited = new boolean[a.length()];
			flag = false;

			for (int i = 0; i < a.length(); i++) {
				temp[i] = a.charAt(i) - '0';
			}
			Arrays.sort(temp, Collections.reverseOrder());

			search(0);

			if(!flag)
				System.out.println(-1);
		}

	}

	private static void search(int idx) {
		if (idx == result.length) {
			String answer = "";
			for (int i = 0; i < result.length; i++) {
				answer += result[i];
			}
			if (Integer.parseInt(answer) < b) {
				System.out.println(answer);
				flag = true;
			}
			return;
		}
		for (int i = 0; i < temp.length; i++) {
			if (!visited[i]) {
				visited[i] = true;
				result[idx] = temp[i];
				if (result[0] == 0)
					return;
				search(idx + 1);
				visited[i] = false;
				if (flag)
					return;
			}
		}
	}
}

 

Main

변수)
a, b : 두 정수 
temp : a를 구성하는 숫자를 저장하는 배열
result : 조합 저장하는 배열
visited : 방문 여부
flag : 답 구한 여부

 

- 두 정수(a, b) 입력

- b의 자릿수 보다 a의 자릿수가 크다면 b보다 작은 수를 만들지 못하므로 -1 출력

- 크지 않다면 a를 구성하는 숫자를 temp 배열에 저장 후 내림차순 정렬 후 search 함수 호출

- flag가 false라면 b보다 작으면서 가장 큰 값을 구하지 못한 것이므로 -1 출력

 

Search

- 조합을 통해 숫자를 구했으면 그 숫자가 b보다 작은지 확인 후 작다면 출력 후 flag를 true로 저장

- temp 배열을 순환

: 아직 사용하지 않은 숫자라면 reuslt에 저장 및 방문 표시

: result의 0번째 값이 0이라면 종료 (C는 0으로 시작하면 안 되기 때문)

: 다음 값을 구하기 위해 search 함수 호출

: 다음 조합을 구하기 위해 방문 표시 해제

: flag가 true라면 이미 답을 구한 것이므로 종료 

---

---