LeetCode 2081: k-Mirror 수의 합 문제 풀이 가이드

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

Vibe Coding

대상자

- 초보 프로그래머 및 알고리즘 학습자

- 수학적 문제 해결 능력 향상이 필요한 개발자

- LeetCode 문제 풀이에 관심 있는 사람들

- 난이도: 중간 (기초 알고리즘과 문자열 조작 지식 필요)

핵심 요약

• k-mirror 수는 10진수와 k진수 모두에서 회문인 수로, 예: 121 (10진수)와 111 (2진수).
• 효율적인 탐색을 위해 10진수 회문 수만 생성하고, k진수로 변환 후 회문 여부를 확인.
• 코드 구조에서 isPalindrome, toBaseK, generate_palindromes 함수가 핵심.
• Python, C++, JavaScript 모두에서 구현 가능하며, n <= 30 이내에서 안정적으로 작동.

섹션별 세부 요약

1. 문제 정의 및 핵심 관찰

• k-mirror 수는 10진수와 k진수에서 모두 회문인 수.
• 모든 10진수 회문 수가 k-mirror 수가 아님 → 검증 필수.
• 10진수 회문 수만 생성해 검색 공간을 줄임.

2. 알고리즘 흐름

• 10진수 회문 수 생성: 1자리 수부터 시작, generate_palindromes 함수 사용.
• k진수로 변환: toBaseK(num, k) 함수를 통해 k진수 표현 생성.
• 회문 여부 확인: isPalindrome(s) 함수로 회문 검증.
• n개 수 찾기: 조건에 맞는 수를 sum에 누적, n개 찾으면 종료.

3. 구현 예시 (Python)

• generate_palindromes() 함수:

```python

def generate_palindromes():

length = 1

while True:

for half in range(10 ((length - 1) // 2), 10 ((length + 1) // 2)):

s = str(half)

yield int(s + s[-2::-1] if length % 2 else s + s[::-1])

length += 1

```

• to_base_k(num, k) 함수:

```python

def to_base_k(num, k):

res = ""

while num:

res = str(num % k) + res

num //= k

return res

```

결론

• 효율성을 위해 10진수 회문 수만 생성하고, k진수 회문 여부를 필터링.
• 핵심 팁: generate_palindromes() 함수로 탐색 공간 줄이기, to_base_k()로 k진수 변환.
• 실무 적용: 알고리즘 최적화와 수학적 문제 해결에 활용 가능.