[리트코드] 3518 - Smallest Palindromic Rearrangement II

3518. Smallest Palindromic Rearrangement II

Hard

---

You are given a palindromic string s and an integer k.

Return the k-th lexicographically smallest palindromic permutation of s. If there are fewer than k distinct palindromic permutations, return an empty string.

Note: Different rearrangements that yield the same palindromic string are considered identical and are counted once.

 

Example 1:

Example 2:

Example 3:

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.
• s is guaranteed to be palindromic.
• 1 <= k <= 106

분류

해시 테이블, 수학, 문자열, 조합론, 카운팅

---

문제 풀이

문제 분석

이 문제는 주어진 팰린드롬 문자열 s와 정수 k를 사용하여 s의 문자들로 만들 수 있는 k번째로 사전식(lexicographically)으로 가장 작은 팰린드롬 순열을 반환하는 문제입니다. 만약 k번째로 작은 순열이 존재하지 않으면 빈 문자열을 반환해야 합니다. 입력 문자열 s는 이미 팰린드롬이라는 점이 중요하며, 소문자 영어 알파벳으로만 구성됩니다. s의 길이는 최대 $10^4$, k는 최대 $10^6$입니다.

핵심 요구사항은 다음과 같습니다:

1. 팰린드롬 순열: s의 문자를 재배열하여 팰린드롬을 만들어야 합니다.
2. 사전식 순서: 가장 작은 것부터 k번째를 찾아야 합니다. 즉, 문자열의 앞부분부터 가능한 한 작은 문자를 배치해야 합니다.
3. 순열 개수 제한: k가 가능한 팰린드롬 순열의 총 개수보다 크면 빈 문자열을 반환해야 합니다.

접근 방법

이 문제는 팰린드롬 생성 규칙과 조합론(permutations)을 이용한 사전식 순서 찾기를 결합해야 합니다.

1. 팰린드롬 구조 이해: 팰린드롬은 "ABCBA"처럼 앞뒤가 같은 문자열입니다. 이는 "ABC" (전반부) + "B" (중앙 문자, 선택 사항) + "CBA" (전반부의 역순) 형태로 구성됩니다.

   • 문자열의 각 문자는 짝수 개씩 존재해야 팰린드롬을 만들 수 있습니다. 단, 문자열의 길이가 홀수일 경우 정확히 하나의 문자만 홀수 개 존재할 수 있으며, 이 문자가 중앙에 위치하게 됩니다.
   • 주어진 s가 이미 팰린드롬이므로, 이러한 조건은 만족합니다.
   • 따라서, 우리는 각 문자의 개수를 세어 짝수 개수만큼은 절반씩 전반부에 사용하고, 홀수 개수인 문자가 있다면 그 문자를 중앙 문자로 사용합니다.

2. 사전식 순서 찾기 (조합론 기반):

   • 사전식으로 k번째 순열을 찾기 위해서는 문자열의 맨 앞부터 차례로 문자를 결정해야 합니다.
   • 맨 앞 문자를 결정할 때, 현재 남은 문자들로 만들 수 있는 팰린드롬의 전반부(half) 순열의 개수를 계산합니다.
   • 각 가능한 문자('a'부터 'z')에 대해, 만약 이 문자를 선택했을 때 뒤에 올 수 있는 순열의 개수가 k보다 크거나 같다면 그 문자를 선택합니다. 그리고 k는 그대로 유지된 채, 남은 문자들로 다음 위치의 문자를 찾습니다.
   • 만약 그 문자를 선택했을 때 뒤에 올 수 있는 순열의 개수가 k보다 작다면, 해당 문자로 시작하는 모든 순열은 k번째 순열보다 사전적으로 앞서므로, k에서 해당 개수만큼 빼주고 다음 문자를 시도합니다.

3. 순열 개수 계산:

   • N개의 자리에 n1개의 char1, n2개의 char2, ... 를 배열하는 경우의 수는 다항 계수(Multinomial Coefficient) 공식을 따릅니다: N! / (n1! * n2! * ...).
   • 이 공식을 사용하여 특정 문자를 선택했을 때 남은 문자들로 만들 수 있는 순열의 개수를 효율적으로 계산해야 합니다.

구현 설명

주어진 코드는 다음 단계로 문제를 해결합니다.

1. 문자 빈도 계산 및 전반부/중앙 문자 준비

• count = Counter(s): 입력 문자열 s의 각 문자 빈도를 계산합니다.
• c = sorted(count.items()): 빈도수가 있는 문자를 알파벳 순서로 정렬합니다. 이는 나중에 사전식으로 문자를 찾을 때 효율적입니다.
• half_dict = {}, mid = "", n = 0: 전반부를 구성할 문자와 그 개수(half_dict), 중앙 문자(mid), 전반부 문자의 총 개수(n)를 초기화합니다.
• for x, y in c: 반복문을 통해 count 맵을 순회하며 half_dict와 mid를 채웁니다.
  • if y // 2 > 0: 문자의 개수가 2개 이상이면 절반은 half_dict에 추가하고 n에 더합니다.
  • if y % 2 == 1: 문자의 개수가 홀수이면 해당 문자를 mid에 저장합니다. (팰린드롬이므로 홀수 개 문자는 최대 하나입니다.)

2. 가능한 총 순열 개수 계산 및 k 값 확인

• p = math.factorial(n): 전반부를 구성하는 n개의 문자를 모두 다르다고 가정했을 때의 순열 개수를 계산합니다.
• for x,y in half_dict.items(): p //= math.factorial(y): half_dict에 있는 각 문자의 중복을 고려하여 p를 다항 계수로 보정합니다. 이렇게 계산된 p는 n개의 문자로 만들 수 있는 전반부 순열의 총 개수를 나타냅니다.
• if p < k: return "": 만약 k가 가능한 총 순열의 개수 p보다 크다면, k번째 순열은 존재하지 않으므로 빈 문자열을 반환합니다.

3. 사전식으로 k번째 전반부 순열 구성

• while n > 0: n은 전반부에 남은 문자의 개수를 의미하며, 이 루프는 n개의 문자를 모두 선택할 때까지 반복됩니다.
• for x in sorted(half_dict.keys()): 현재 half_dict에 남아있는 문자를 알파벳 순서대로 시도합니다.
  • y = half_dict[x]: 현재 문자의 남은 개수를 가져옵니다.
  • if y > 0: 만약 해당 문자를 사용할 수 있다면 (y가 0보다 크다면).
    • w = p * y // n: 현재 p는 남은 n개의 문자로 만들 수 있는 총 순열 개수입니다. 만약 문자 x를 선택한다면, 남은 n-1개의 문자로 만들 수 있는 순열 개수는 p * (y/n)이 됩니다. 이 w는 x로 시작하는 순열의 개수입니다.
    • if k <= w: k가 w보다 작거나 같다면, 우리가 찾는 k번째 순열은 현재 x로 시작해야 합니다.
      • answer.append(x): x를 정답 문자열의 전반부에 추가합니다.
      • half_dict[x] -= 1: x를 하나 사용했으므로 개수를 줄입니다.
      • p = w: 이제 남은 n-1개의 문자로 k번째 순열을 찾아야 하며, 총 순열 개수는 w로 갱신됩니다.
      • n -= 1: 남은 문자의 개수를 하나 줄입니다.
      • break: 현재 위치의 문자를 찾았으므로 다음 위치의 문자를 찾기 위해 내부 for 루프를 종료하고 while 루프의 다음 반복으로 넘어갑니다.
    • else: k -= w: k가 w보다 크다면, x로 시작하는 w개의 순열은 모두 k번째 순열보다 사전적으로 앞서므로, k에서 w를 빼고 다음 문자를 시도합니다.

4. 최종 팰린드롬 문자열 생성

• tmp_reverse = answer[::-1]: answer에 저장된 전반부를 역순으로 만듭니다.
• if mid: answer.append(mid): 중앙 문자가 있다면 answer의 끝에 추가합니다.
• return ''.join(answer + tmp_reverse): 전반부, 중앙 문자 (선택 사항), 그리고 전반부 역순을 합쳐 최종 팰린드롬 문자열을 만듭니다.

⏱복잡도 분석

• 시간 복잡도: O(L + C^2 * L/2) -> O(L) (상수 C=26)

  • Counter(s): 문자열 s의 길이를 L이라고 할 때, O(L) 시간이 소요됩니다.
  • sorted(count.items()): 알파벳 크기 C (26)에 대해 O(C log C) 시간이 소요됩니다. 이는 상수 시간이므로 O(1)로 간주할 수 있습니다.
  • half_dict 및 mid 초기화: C개의 항목을 순회하므로 O(C) 시간이 소요됩니다.
  • math.factorial(n) 및 p //= math.factorial(y): n은 L/2까지 커질 수 있습니다. math.factorial은 내부적으로 숫자의 크기에 비례하는 시간이 걸리지만, 이 문제는 k가 $10^6$ 이하이므로 p의 절대값이 커질 수 있어도, p * y // n 연산 자체가 Python의 큰 정수 처리 덕분에 효율적으로 수행됩니다. 전체 과정에서 각 문자의 팩토리얼은 C번 호출되고, n의 팩토리얼은 1번 호출됩니다.
  • while n > 0 루프: 이 루프는 n이 0이 될 때까지 실행됩니다. n은 전반부의 길이이므로 최대 L/2번 반복됩니다.
  • for x in sorted(half_dict.keys()) 내부 루프: 알파벳 크기 C (26)만큼 반복됩니다.
  • 내부 연산 (p * y // n, append, -=, break 등): 모두 상수 시간 O(1)에 수행됩니다.
  • 최종 문자열 join: O(L) 시간이 소요됩니다.
  • 따라서 전체 시간 복잡도는 O(L + C + (L/2 * C)) 가 됩니다. C가 상수(26)이므로 O(L)로 근사할 수 있습니다.

• 공간 복잡도: O(L)

  • count 딕셔너리: 최대 C (26)개의 문자를 저장하므로 O(C) 공간을 사용합니다.
  • half_dict: 마찬가지로 O(C) 공간을 사용합니다.
  • answer 리스트: 최대 L/2개의 문자를 저장하므로 O(L) 공간을 사용합니다.
  • tmp_reverse: answer와 같은 크기이므로 O(L) 공간을 사용합니다.
  • 따라서 전체 공간 복잡도는 O(L)입니다.

핵심 포인트

1. 팰린드롬 구조 활용: 팰린드롬은 전반부, 중앙 문자(선택 사항), 전반부 역순으로 구성된다는 점을 이해하고, 주어진 문자로 만들 수 있는 전반부 문자 조합 (half_dict)과 중앙 문자 (mid)를 효율적으로 분리하는 것이 중요합니다.
2. 조합론을 이용한 사전식 순열 찾기: k번째 순열을 찾기 위해 문자열의 각 위치에 올 문자를 'a'부터 순서대로 시도하며, 해당 문자를 선택했을 때 남은 문자들로 만들 수 있는 순열의 개수(w)를 계산합니다. 이 w와 k를 비교하여 현재 위치의 문자를 확정하고 k 값을 업데이트하는 방식이 핵심입니다.
3. 다항 계수 및 효율적인 순열 개수 업데이트: p = n! / (n1! * n2! * ...) 공식을 활용하여 총 순열 개수를 계산하고, 특정 문자를 선택했을 때의 새로운 순열 개수 w를 p * (y / n)으로 효율적으로 업데이트하는 것이 성능에 결정적인 역할을 합니다. 반복적으로 math.factorial을 호출하지 않아도 되어 계산 비용을 크게 줄일 수 있습니다.

풀이 코드

import math
from collections import Counter

class Solution:
    def smallestPalindrome(self, s: str, k: int) -> str:
        count = Counter(s)
        c = sorted(count.items())
        
        answer = []
        mid = ""
        
        half_dict = {}
        n = 0
        
        for x, y in c:
            if y // 2 > 0:
                half_dict[x] = y // 2
                n += y // 2
            if y % 2 == 1:
                mid = x
                
        p = math.factorial(n)
        for x,y in half_dict.items():
            p //= math.factorial(y)
            
        if p < k:
            return ""
            
        while n > 0:
            for x in sorted(half_dict.keys()):
                y = half_dict[x]
                if y > 0:
                    w = p * y // n
                    
                    if k <= w:
                        answer.append(x)
                        half_dict[x] -= 1
                        p = w
                        n -= 1
                        break
                    else:
                        k -= w
                        
        tmp_reverse = answer[::-1]
        if mid:
            answer.append(mid)
            
        return ''.join(answer + tmp_reverse)