문제 설명
숫자 n과 값 k가 주어진다고 가정해 봅시다. 이때 '0', '1', '2' 세 문자만으로 구성되면서 같은 문자가 연속해서 나오지 않는 길이 n의 문자열을 생각해 보겠습니다. 이 조건을 만족하는 문자열들 중에서 사전순(lexicographical order)으로 k번째에 해당하는 문자열을 찾아야 하며, 만약 k번째 문자열이 존재하지 않는다면 빈 문자열을 반환하면 됩니다.
예를 들어 입력이 n = 4, k = 2라면 출력은 "0120"이 됩니다.
풀이 접근 방법
이 문제는 재귀 호출을 이용해 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 길이가 s인 문자열에서 첫 번째 문자를 하나로 고정하면, 나머지 s-1개의 각 자리에는 직전 문자와 다른 문자 2가지만 선택할 수 있습니다. 따라서 각 시작 문자마다 정확히 2^(s-1)개의 유효한 문자열이 존재합니다.
- 이 개수를 기준으로 k가 현재 문자가 담당하는 범위 안에 속하는지 판단합니다. 속한다면 해당 문자를 선택하고 나머지 부분을 재귀적으로 결정하고, 그렇지 않다면 k에서 2^(s-1)을 빼고 다음 문자로 넘어갑니다.
구체적인 절차는 다음과 같습니다.
- solve() 메서드를 정의합니다. 이 메서드는 s, k, 그리고 직전에 사용한 문자인 last를 매개변수로 받습니다.
- s가 0이면 빈 문자열을 반환합니다.
- "012"의 각 문자 c에 대해 다음을 수행합니다.
- c가 last와 같으면 건너뜁니다(연속 반복 방지).
- k가 2^(s-1)보다 작으면 c + solve(s - 1, k, c)를 반환합니다.
- 그렇지 않으면 k에서 2^(s-1)만큼 뺍니다.
- 모든 문자를 확인한 후에도 답을 찾지 못했다면 빈 문자열을 반환합니다.
- 메인 부분에서 solve(n, k, None)을 호출해 결과를 얻습니다.
아래 예제 코드를 통해 더 잘 이해해 보겠습니다.
예제 코드
class Solution:
def solve(self, s, k, last=None):
if s == 0:
return ""
for c in "012":
if c == last:
continue
if k < 2 ** (s - 1):
return c + self.solve(s - 1, k, c)
k -= 2 ** (s - 1)
return ""
ob = Solution()
n = 4
k = 2
print(ob.solve(n, k))
입력
4, 2
출력
0120
동작 원리 정리
n = 4, k = 2인 경우를 살펴보면, 첫 문자 '0'으로 시작하는 유효한 문자열은 총 2³ = 8개입니다. k가 이 범위 안에 있으므로 첫 문자로 '0'을 확정하고, 남은 길이 3에 대해 같은 과정을 반복합니다. 각 단계에서 직전 문자와 같은 문자는 건너뛰기 때문에 자동으로 "같은 문자가 연속해서 등장하지 않는" 조건이 유지됩니다. 만약 k가 모든 가능한 문자열의 개수를 초과하면 재귀 호출 전체가 빈 문자열을 반환하게 되어, 존재하지 않는 경우도 자연스럽게 처리됩니다.