[백트래킹/자바] 코드트리 IL. 아름다운 수

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

이 문제는 모든 경우의 수를 순회하면서 '아름다운 수'인지 판단하고, 그 수를 세는 문제이다. n도 10 이하의 자연수이므로 완전 탐색 알고리즘 중 하나를 사용하는 것이 합리적이다.

 

그 중에서 이번에는 n에 따라 파악해야 하는 대상 숫자의 자릿수가 변동되므로 완전탐색 중 백트래킹을 이용하여 경우의 수를 탐색하고, 탐색된 경우의 수가 '아름다운 수'인지 확인하는 함수를 작성해서 true일 때마다 count할 수 있도록 연산하면 된다.

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;


public class Main {
    private static int n;
    private static int ans = 0;
    private static List<Integer> li = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        choose(1);
        System.out.println(ans);
    }

    private static void choose(int x) {
        if (x == n + 1) {
            if (isBeautifulNum(li)) {
                ans++;
            }
            return;
        }
        x++;
        for (int k = 1; k <= 4; k++) {
            li.add(k);
            choose(x);
            li.remove(li.size() - 1);
        }
    }

    private static boolean isBeautifulNum(List<Integer> li) {
        for (int i = 0; i < li.size(); i++) {
            Integer elem = li.get(i);
            if (elem == 1) {
                continue;
            } else if (elem == 2) {
                if (inRange(i + 1)) {
                    Integer nextElem = li.get(i + 1);
                    if (elem.equals(nextElem)) {
                        i = i + 1;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            } else if (elem == 3) {
                if (inRange(i + 2)) {
                    Integer nextElem = li.get(i + 1);
                    Integer thirdElem = li.get(i + 2);
                    if (elem.equals(nextElem) && nextElem.equals(thirdElem)) {
                        i = i + 2;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            } else if (elem == 4) {
                if (inRange(i + 3)) {
                    Integer nextElem = li.get(i + 1);
                    Integer thirdElem = li.get(i + 2);
                    Integer fourthElem = li.get(i + 3);
                    if (elem.equals(nextElem) && nextElem.equals(thirdElem) && thirdElem.equals(fourthElem)) {
                        i = i + 3;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean inRange(int i) {
        return i >= 0 && i < n;
    }
}

위 로직이 바로 떠오른 가장 1차원적인 로직이었습니다. 하지만 위 로직은 2,3,4에 대해 생짜로 하드코딩을 해서 구현한 상황입니다.

통과는 하였지만, 로직적으로 딱히 완성도 높은 로직은 아니라고 생각됩니다.

 

차근차근 생각해보면 위와 같은 상황은 반복되는 부분이 arr[i] == arr[i+1] 맥락이 반복되며, 그 숫자 만큼 i = i + k 만큼 되는 것을 알 수 있습니다.

 

따라서 위 로직은 다음과 같이 개선될 수 있습니다.

public class Main {
    
    ...

    private static boolean isBeautifulNum(List<Integer> li) {
        for (int i = 0; i < li.size(); i++) {
            Integer elem = li.get(i);
            while (--elem > 0) {
                if (inRange(i + 1)) {
                    Integer nextElem = li.get(i + 1);
                    if (elem.equals(nextElem)) {
                        i = i + 1;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        return true;
    }

	...
}

위와 같이 개선하니까 조금이지만 실행 속도 또한 향상된 것을 알 수 있었습니다.