K-th 문자 찾기 LeetCode 풀이 가이드
AI Store에서 AI코딩으로 만들어진 앱을 만나보세요!
지금 바로 방문하기

"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=5k-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) 시간 복잡도로 해결
  • 문제 해결 전략:
  • 이진수 패턴 인식 → 수학적 공식 도출 → 효율적 구현
  • "문제의 핵심은 시뮬레이션을 피하는 것"이라는 핵심 교훈 제공