[백준] 1038 - 감소하는 수 (JAVA)

1. 소요시간 : 25분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 5
4. 문제 유형 : 브루트포스 알고리즘, 백트래킹
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/1038
8. 푼 날짜 : 2023.03.31

1. 사용한 자료구조 & 알고리즘

백트래킹과 정렬을 사용했다.

2. 사고과정

브루트포스 알고리즘 카테고리를 클릭해서 왔기에 문제를 보자마자 백트래킹일 것이라고 생각했다.
아마 카테고리를 모르고 왔다면 DP와 백트래킹 문제 중 헷갈렸을 것 같다.
처음에는 만약 나의 마지막자리 숫자와 0~9까지를 비교해서
0~9까지가 더 작다면 내 숫자에 0~9를 추가하여 탐색하는 방식으로 진행했다.

🧐 예를 들어서 내가 943 이면 0~9까지를 943의 마지막 자리 숫자인 3과 비교한다. 3보다 더 작은 것은 0,1,2 가 올 수 있고 그렇다면 9430, 9431, 9432 의 방향으로 가지수를 계속 뻗어나간다.

3. 풀이과정

1. 일단 초기식으로 0~9까지는 전부 백트래킹으로 탐색
2. 앞서 말한 내 끝자리 수와 0~9를 비교. 그렇게 계속 탐색함.
3. 더 이상 탐색하지 못한다면 모든 백트래킹이 종료.
4. 백트래킹 할 때마다 ArrayList 에 숫자를 넣고, 정렬함.
5. 이제 n으로 숫자를 받고, ArrayList의 n번째 인덱스 값을 출력
6. n이 ArrayList의 size 보다 크다면 -1 출력.

4. 소스코드

import java.util.*;
import java.io.*;
public class Main {

	static ArrayList<Long> number=new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		for(int i=0;i<=9;i++) {
			number.add((long) i);
			backtracking(Integer.toString(i));
		}
		
		Collections.sort(number);

		
		int n=Integer.parseInt(br.readLine());
			
		
		
		if(n>=number.size()) System.out.println(-1);
		else
			System.out.println(number.get(n));


	}
	public static void backtracking(String num) {
		
		

		for(int i=0;i<9;i++) {
			int lastnum=num.charAt(num.length()-1)-'0';
			if(i<lastnum) {
				number.add(Long.parseLong(num)*10+i);
				backtracking(num+i);
			}
		}



	}
}

5. 결과

4개를 제출했는데 각각 이유가 있다.
👉 첫 번째 제출 : ArrayList를 int 형으로 선언. 잘 되다가 40% 쯤에서 틀림. 예외가 뭘까 생각해 봤는데 9,876,543,210 이 예외였음. 98억으로 21억의 int 값을 넘어감.
👉 두 번째 제출 : 그렇다면 ArrayList를 String 형으로 하면 되지 않을까 ? 제출 했는데 틀림. 왜 그럴까 출력해 봤는데 String 형은 정렬할 때 우리가 아는 숫자 순서대로 정렬하지 않음. 그래서 틀림
👉 세 번째 제출 : 그럼 98억까지고 그보다 더 큰 숫자는 나올 수 없으므로 long으로 제출함. 정답.
👉 네 번째 제출 : 최적화 하기. 처음에 초기식으로는 0~9까지를 넣지만 내 숫자보다 낮은 숫자를 탐색할 때에는 9는 탐색하지 않아도 됨. 즉 탐색을 0~8까지만 탐색하므로 탐색 범위를 1 줄임.
🧐 제출했는데 세 번째 제출과 시간 차이가 크게 다르지 않았음. 이유는 그냥 검사만 하나 더 할 뿐이고 9로 계속해서 가지를 뻗어나가지는 않으므로 그럴 것으로 추정.

6. 회고

이 문제는 백트래킹 스도쿠 문제와 비슷한 것 같다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212