[자바] 백준 1038 - 감소하는 수 (java)

 문제 : boj1038

---

 

필요 알고리즘 개념

•  브루트포스
  • 모든 경우의 수를 살펴보는 브루트포스 개념을 알고 있어야 한다. 브루트포스 글
• 백트래킹
  
  • 브루트포스에서 모든 경우를 볼 때, 중간에 답이 될 가능성이 없는 부분을 제외시켜 시간복잡도를 낮추는 백트래킹 개념에 대해 알고 있어야 한다. 백트래킹 글

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 이 문제에서 나올 수 있는 가장 큰 감소하는 수가 '9876543210'임은 생각해볼 수 있다. 그렇다면 최대 10자리에 대해 브루트포스로 모든 경우를 보는 경우를 생각해보자. 아래 코드처럼 생성할 수 있을 것이다. 파라미터부터 보면 goal은 확인하려는 최종 자리수이다(1자리 수 부터 10자리 수까지). idx는 현재 자리수이다. cur은 현재까지 만들어진 값이다. 그리고 base condition으로 목표 자리수(goal) == 현재 자리수(idx)가 되었다면, 감소하는 수인지 확인하고(isDesc()) 배열(arr)에 넣어둘 것이다. 그럼 dfs로 goal을 1~10에 대해 돌려주면 구할 수 있을 것 같다!

private void dfs(int goal, int idx, int cur) {
    if (goal == idx) {
    	if (isDesc(cur))
        	arr.add(cur);
        return;
    }
    for (int i = cur==0?1:0; i <= 9; i++) {
        int tmp = cur*10+i;
        dfs(goal, idx+1, tmp);
    }
}

하지만 위처럼 모든 경우를 보게되면 O(10^10)이 될 것이므로 통과할 수 없다.

 

 

  잘 생각해보면, 현재값 cur을 알고 있고 매번 1의자리수 위치에 새로운 수를 붙일 것이다. 따라서 매번 1의자리 수 보다 작은 수에 대해서만 붙여보면, isDesc()는 아예 필요가 없다. 예를들어 현재 값이 '654'이고 그 뒤에 수 하나를 더 붙이려 한다면 4보다 작은 3,2,1,0만 붙여보면 될 것이다. 그럼 재귀함수를 한번 정의해보자. limit이 제한 자리수를 정한 부분이다.

private void dfs(int goal, int idx, int cur) {
    if (goal == idx) {
        arr.add(cur);
        return;
    }
    int limit = cur==0 ? 9 : (int)(cur%10-1);
    for (int i = cur==0?1:0; i <= limit; i++) {
        int tmp = cur*10+i;
        dfs(goal, idx+1, tmp);
    }
}

  위처럼 브루트포스에 백트래킹 개념을 넣어주고 한번 돌려보면, 사실 모든 경우가 1000개 정도밖에 없음을 알 수 있다. 따라서 실제 계산된 시간복잡도와 관계없이 매우 빠른시간 내에 모든 경우를 볼 수 있다.

 

 

 

  또 다른 방법도 있는데, 재귀함수에 대해 익숙하지 않으면 위처럼 짜기 힘들 수 있다. 그럼 또 다른 방법이 있는데, brute force 방식으로 짜면 한 50~100초정도 걸릴텐데, 위에서 말했듯이 어차피 1000개 정도밖에 없다. 그러므로 그걸 코드에 그대로 박아넣어도 통과가 가능하다. 그럼 아래처럼 된다.(통과했다)

  물론 정해는 백트래킹이지만, 속도가 가장 빠른건 이 방법이긴하다. 전체 프로그램 시간복잡도가 입력받기 O(1), 답 출력  O(1) 이다.ㅋㅋㅋ

 

 

  아, 주의점은 10자리 수 9876543210은 int형으로 표현 불가하다. 내 경우엔 그래서 그 값만 String으로 처리했다. 그냥 long으로 해도 통과에 전혀 상관 없다.

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    ArrayList<Integer> arr = new ArrayList<>();

    private void dfs(int goal, int idx, int cur) {
        if (goal == idx) {
            arr.add(cur);
            return;
        }
        int limit = cur==0 ? 9 : (int)(cur%10-1);
        for (int i = cur==0?1:0; i <= limit; i++) {
            int tmp = cur*10+i;
            dfs(goal, idx+1, tmp);
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr.add(0);
        for (int goal = 1; goal <= 9; goal++) {
            dfs(goal, 0, 0);
        }
        int n = Integer.parseInt(br.readLine());
        if (n == arr.size()) {
            System.out.println("9876543210");
            return;
        }
        try {
            System.out.println(arr.get(n));
        } catch (IndexOutOfBoundsException e) {
            System.out.println(-1);
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}