본문으로 건너뛰기

2081 - Sum of k-Mirror Numbers

info

풀이 키워드​

스포주의

구현


풀이 코드​

info
  • 메모리: 44390 KB
  • 시간: 448 ms
class Solution {
    int k, n;
    List<Long> numList;

    // 1. gen base-k palindrome
    // 2. convert to base-10 & check palindrome
    public void gen(List<Integer> prefix, int remain, boolean isOdd) throws Exception {
        if (remain == 0) {
            List<Integer> digits = new ArrayList<>(prefix);
            int mid = isOdd ? prefix.size()-1 : prefix.size();
            for (int i = mid-1; i > -1; --i) {
                digits.add(prefix.get(i));
            }

            long num10 = 0;
            for (int d : digits) num10 = num10 * k + d;

            String s = Long.toString(num10);
            for (int l = 0, r = s.length()-1; l < r; ++l, --r)
                if (s.charAt(l) != s.charAt(r)) return;

            numList.add(num10);
            if (numList.size() >= n) throw new Exception();
            return;
        }

        for (int i = 0; i < k; ++i) {
            prefix.add(i);
            gen(prefix, remain-1, isOdd);
            prefix.remove(prefix.size()-1);
        }
    }

    public long kMirror(int k, int n) {
        this.k = k;
        this.n = n;
        numList = new ArrayList<>();

        try {
            for (int len = 1; ; ++len) {
                int half = (len + 1) >> 1;
                for (int i = 1; i < k; ++i) {
                    List<Integer> prefix = new ArrayList<>();
                    prefix.add(i);
                    gen(prefix, half-1, (len&1)==1);
                }
            }
        } catch (Exception e) {}

        long ans = 0;
        for (int i = 0; i < n; ++i) ans += numList.get(i);

        return ans;
    }
}

풀이 해설​

어떤 수를 10진수, k진수로 나타내었을 때 둘 다 팰린드롬일 경우 k-Mirror 수라고 한다.

총 n개의 k-Mirror 수를 반환하면 되는 문제이다.

우선 문제 풀이를 크게 3단계로 나눌 수 있다.

  1. 팰린드롬인 k진수 수 생성
  2. 해당 수를 10진수로 변환
  3. 변환된 10진수도 팰린드롬이면 정답 리스트에 추가

여기서 1번을 위해 재귀를 사용하고, TLE를 고려하여 재귀는 팰린드롬 길이의 절반까지만 수행한다.

prefix digit의 조합을 구하는 과정에서 함수 gen은 원소추가 -> 재귀 -> 원소제거 순의 메인 로직을 가지고 있는데,

상단의 2, 3번의 과정 때문에 아래와 같이 base case 처리가 메인 로직보다 복잡하게 나온다.

base case 전체 로직
if (remain == 0) {
    List<Integer> digits = new ArrayList<>(prefix);
    int mid = isOdd ? prefix.size()-1 : prefix.size();
    for (int i = mid-1; i > -1; --i) {
        digits.add(prefix.get(i));
    }

    long num10 = 0;
    for (int d : digits) num10 = num10 * k + d;

    String s = Long.toString(num10);
    for (int l = 0, r = s.length()-1; l < r; ++l, --r)
        if (s.charAt(l) != s.charAt(r)) return;

    numList.add(num10);
    if (numList.size() >= n) throw new Exception();
    return;
}

📌 base case 로직 설명​

1. mirror 하기
List<Integer> digits = new ArrayList<>(prefix);
int mid = isOdd ? prefix.size()-1 : prefix.size();
for (int i = mid-1; i > -1; --i) {
    digits.add(prefix.get(i));
}

prefix를 다 구했다면 팰린드롬 전체 길이의 홀짝여부에 따라 잘 mirror해서 digits에 담아준 뒤
(-> 홀수면 맨 마지막 prefix는 정 가운데 수라서 mirror 대상 아니게 됨)

2. 10진수 변환 및 검사
long num10 = 0;
for (int d : digits) num10 = num10 * k + d;

String s = Long.toString(num10);
for (int l = 0, r = s.length()-1; l < r; ++l, --r)
    if (s.charAt(l) != s.charAt(r)) return;

numList.add(num10);

10진수 변환 및 팰린드롬인지 검사해주고, 통과 못하면 다음 조합 탐색으로 넘어간다.

3. 즉시 탈출 or 우아한 탈출
if (numList.size() >= n) throw new Exception();
return;

반대로 통과하면 numList에 원소가 추가되므로 이 때 구할만큼 다 구했는지 판단 후

다 구했으면 탐색을 graceful exit 하지 않고 abrupt exit한다.


메모​

  • 단순 구현과 빡구현의 중간 그 쯤 어딘가
  • 팰린드롬 길이의 절반까지만 조합을 구하고 이후는 mirror해서 붙이는게 핵심이다. 전체 길이를 재귀로 처리하려고 하면 TLE 발생함
    • hard 문제 대부분이 시간복잡도 빡세게 잡는듯