"K-th 문자 찾기" 문제 풀이 가이드
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
알고리즘
대상자
- 초보 프로그래머 (LeetCode 문제 풀이 경험자)
- 비트 연산, 패턴 인식 기초 지식 보유자
- 문자열 시뮬레이션 대신 수학적 접근을 선호하는 개발자
핵심 요약
- 문제 핵심:
k-1
의 이진 표현에서1
의 개수(popcount
)를 계산해'a'
에 더함 popcount(k-1)
→'a' + popcount(k-1)
- 시간 복잡도:
O(1)
(모든 단계 시뮬레이션 없이 수학적 공식 적용) - 코드 예시:
```cpp
char kthCharacter(unsigned k) { return 'a' + popcount(k - 1); }
```
```python
def kthCharacter(self, k: int) -> str: return chr(ord('a') + bin(k-1).count('1'))
```
섹션별 세부 요약
1. 문제 정의
- 초기 조건:
word = "a"
로 시작 - 변환 규칙:
word
의 각 문자를 알파벳 다음 문자로 변환 후, 원래 문자열에 추가- 예:
"a"
→"ab"
,"ab"
→"abbc"
- 목표:
k
-번째 문자(1-based 인덱스)를 반환
2. 패턴 인식
- 변환의 결정성:
- 각 문자의 다음 문자는 알파벳 순서로 고정
- 이진수의
1
의 개수로 위치 계산 가능 - 이진수와의 관계:
k-1
의 이진 표현에서1
의 개수 =k
-번째 문자의'a'
로부터의 오프셋
3. 최적화된 접근법
- 시뮬레이션 대체:
- 문자열 생성 대신
popcount(k-1)
계산 - 예:
k=5
→k-1=4
(이진100
) →1
의 개수 1 →'a' + 1 = 'b'
- 코드 구현:
- C++:
popcount()
함수 사용 - Python:
bin(k-1).count('1')
- JavaScript:
toString(2).split('1').length - 1
결론
- 핵심 팁: 시뮬레이션 대신
popcount(k-1)
공식을 활용해O(1)
시간 복잡도로 해결 - 문제 해결 전략:
- 이진수 패턴 인식 → 수학적 공식 도출 → 효율적 구현
- "문제의 핵심은 시뮬레이션을 피하는 것"이라는 핵심 교훈 제공