초보자 친화적인 가이드: "k-미러 수의 합" - LeetCode 2081 (Python, JavaScript)
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
인공지능
대상자
- 프로그래밍 초보자 및 알고리즘 문제 풀이 준비자
- 난이도: 중간 (기초 알고리즘과 문자열 처리 지식 필요)
핵심 요약
- k-미러 수는 10진수와 k진수 모두에서 회문인 수로, 이 수들의 합을 구하는 문제
- 효율성을 위해 10진수 회문 수만 생성하고, k진수로 변환 후 회문 여부 확인
- C++/JavaScript 예제 코드 제공: 회문 생성 및 검증 로직 포함
섹션별 세부 요약
1. 문제 개요
- 입력값:
k
(진수),n
(찾을 k-미러 수 개수) - 출력값:
n
개의 k-미러 수의 합 - k-미러 수 조건:
- 10진수와 k진수 모두에서 회문
- 예:
121
은 10진수 회문,k=2
일 때111101
(2진수)도 회문이면 k-미러 수
2. 핵심 아이디어
- 모든 수를 검사하는 대신 10진수 회문 수만 생성해 검색 공간을 줄임
- 10진수 회문 생성 전략:
- 1자리 수부터 시작, 길이 증가하며 생성
- 예:
1
,2
, ...,9
,11
,22
,101
,111
, ...
3. 접근 방법
- 10진수 회문 생성:
half
부분 생성 후, 반전한 문자열로 전체 생성 (예:half=12
→12
+21
→1221
)- k진수로 변환:
toBaseK
함수 사용 (예:num=1221
,k=2
→1001100101
)- 회문 여부 확인:
isPalindrome
함수로 문자열 비교
4. 코드 구현 예시
- C++ 코드:
toBaseK
함수:num % k
로 나머지 계산 후 역순isPalindrome
함수: 문자열과 역순 문자열 비교- JavaScript 코드:
toBaseK
함수:num.toString(k)
사용isPalindrome
함수:s.split('').reverse().join('')
활용
결론
- 효율적인 풀이를 위해 10진수 회문 수만 생성하고, k진수로 변환 후 회문 여부 검증
- C++/JavaScript 예제 코드는 회문 생성 로직과 변환 함수를 포함해 직접 구현 가능
- 문자열 조작과 진법 변환 기술을 통해 문제 해결 가능