[코드트리] 아름다운 수(Java)

문제 링크

https://www.codetree.ai/missions/2/problems/beautiful-number?&utm_source=clipboard&utm_medium=text

내 코드

import java.util.*;

public class Main {
    static int n;

    static int ans = 0;
    static ArrayList<Integer> list;

    static boolean isBeautilful() {
        for (int i = 0; i < n; i++) {
            int cur = list.get(i);
            int count = 0;
            int curIdx = i;

            while (curIdx < n && list.get(curIdx) == cur) {
                count++;
                curIdx++;
            }

            // 동일한 숫자만 존재하는 경우
            if (i == 0 && curIdx == n) {
                count %= cur;
                if (count == 0) {
                    return true;
                }
                else return false;
            }

            if (cur == 1) continue;

            if (count != cur && count % cur != 0) {
                return false;
            }

            // while문에서 읽은만큼 건너뛰기
            i = curIdx-1;
        }

        return true;
    }

    static void makeNum(int cnt) {
        if (cnt == n) {

            if (isBeautilful()) {
                // for (int i = 0; i < n; i++) System.out.print(list.get(i));
                // System.out.println();
                ans++;
            }
            return;
        }

        for (int i = 1; i <= 4; i++) {
            list.add(i);
            makeNum(cnt+1);
            list.remove(list.size()-1);
        }

    }

    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        list = new ArrayList<>();
        makeNum(0);
        System.out.println(ans);
    }
}

설명

1. 재귀함수를 통해서 1~4 숫자로 만든 n자리 수를 만든다
2. 각 숫자에 대해서 아름다운지 판단한다

makeNum()

• 가능한 모든 n자리 숫자 생성

• n자리가 되었을 때, 아름다운지 판단

isBeautilful()

• 각 숫자에서 연속된 숫자의 개수를 센다 -> count에 저장 & curIdx에는 연속된 마지막 숫자의 다음 인덱스

• 만약 처음부터 끝까지 같은 숫자인 경우, 동일한 숫자에 대해 연달아 같은 숫자의 묶음이 나오는지 확인한다

  • 나머지 값이 0이면 묶음이 정확히 나눠 떨어진다는 의미 -> true

  • 0이 아니면 나눠 떨어지지 않음 -> false

• 만약 현재 값이 1이라면 continue

  • 1이 1번 연속하여 나온거니깐 통과

• 만약 현재 값(cur)만큼 연속되지 않았고, 묶음도 아닌 경우 -> false

• 위의 경우를 모두 통과했다면, 딱 현재 값만큼 연속되어서 숫자가 나타났다고 볼 수 있다.

• 그래서 연속된 숫자를 조회했으니깐 조회한만큼 건너뛰기 위해 i = curIdx - 1를 한다.

  • -1을 하는 이유는 curIdx는 다음에 조회할 인덱스가 들어가 있다.
  • for문에서 i++ 를 하기 때문에, -1을 진행한다.