[리트코드] 3517 - Smallest Palindromic Rearrangement I

3517. Smallest Palindromic Rearrangement I

Medium

---

You are given a palindromic string s.

Return the lexicographically smallest palindromic permutation of s.

 

Example 1:

Example 2:

Example 3:

 

Constraints:

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

분류

문자열, 정렬, Counting Sort

---

문제 풀이

문제 분석

주어진 문자열 s는 이미 팰린드롬(palindrome)입니다. 이 문자열의 문자들을 재배열하여 사전순으로 가장 작은 팰린드롬을 만들어 반환해야 합니다.

• 입력: 소문자 알파벳으로 이루어진 팰린드롬 문자열 s (길이 1 ~ 100,000)
• 출력: s의 문자로 구성된 사전순 최소 팰린드롬 문자열

팰린드롬의 특성상 문자 빈도수는 최대 한 개의 홀수 개 문자를 제외하고 모두 짝수 개여야 합니다. 사전순으로 가장 작게 만들기 위해서는 앞쪽 절반에 사전순으로 앞선 문자들을 최대한 많이 배치해야 합니다.

---

접근 방법

자료구조: Counter (해시 맵)를 사용하여 각 문자의 출현 횟수를 셉니다.
알고리즘: Counting Sort / Greedy 방식을 사용합니다.

1. 빈도수 계산: Counter로 각 문자의 개수를 셉니다. (O(N))
2. 정렬: 문자를 사전순(a~z)으로 정렬합니다. (고유 문자 최대 26개이므로 O(1) 또는 O(26 log 26))
3. 앞쪽 절반 구성: 정렬된 순서대로 각 문자를 빈도수 // 2 만큼 결과 리스트에 추가합니다. 이렇게 하면 사전순으로 가장 작은 앞쪽 절반이 만들어집니다.
4. 중앙 문자 처리: 홀수 개수인 문자가 있다면(최대 1개), 이를 중앙에 배치합니다.
5. 뒤쪽 절반 구성: 앞쪽 절반을 뒤집어서 뒤에 붙이면 팰린드롬이 완성됩니다.

이 접근법은 사전순 최소 조건을 만족시키기 위해 '가장 작은 문자를 가능한 한 앞쪽에 배치한다'는 그리디 전략을 사용합니다.

---

구현 설명

1단계: 문자 빈도수 계산 및 정렬

count = Counter(s)
c = sorted(count.items())

• Counter(s)로 각 알파벳의 출현 횟수를 딕셔너리 형태로 얻습니다.
• sorted(count.items())를 호출하여 (문자, 개수) 쌍을 문자 기준 오름차순(a~z)으로 정렬합니다. 이 정렬 순서가 사전순 최소 팰린드롬을 만드는 핵심입니다.

2단계: 앞쪽 절반 문자열 구성 및 중앙 문자 결정

answer = []
mid = ""

for x, y in c:
    for i in range(y // 2):
        answer.append(x)
    if y % 2 == 1:
        mid = x

• 정렬된 문자 순서대로 반복하며, 각 문자를 y // 2 횟수만큼 answer 리스트에 추가합니다. 이것이 팰린드롬의 왼쪽 절반이 됩니다.
• 개수 y가 홀수인 경우 해당 문자 x를 mid 변수에 저장합니다. 문제 조건상 팰린드롬이므로 홀수 개 문자는 최대 1개만 존재하며, 마지막에 저장된 값이 중앙에 위치하게 됩니다. (사전순 정렬 중 홀수 개 문자는 어차피 1개뿐이므로 순서 무관)

3단계: 뒤쪽 절반 생성 및 최종 조립

tmp_reverse = answer[::-1]
if mid:
    answer.append(mid)
return ''.join(answer + tmp_reverse)

• answer[::-1]로 왼쪽 절반을 뒤집어 오른쪽 절반(tmp_reverse)을 만듭니다.
• 중앙 문자 mid가 존재하면 왼쪽 절반 뒤에 붙입니다.
• 최종적으로 왼쪽 절반 + 중앙 문자(선택) + 오른쪽 절반 순서로 연결하여 문자열로 반환합니다.

---

⏱복잡도 분석

• 시간 복잡도: O(N)

  • Counter(s) 생성: O(N) (N = 문자열 길이)
  • sorted(count.items()): 고유 문자는 최대 26개(소문자)이므로 O(26 log 26) ≈ O(1)
  • 이중 루프(for x,y in c + for i in range(y//2)): 총 반복 횟수는 모든 문자의 개수 합의 절반인 N/2이므로 O(N)
  • 리스트 뒤집기 및 조인: O(N)
  • 전체적으로 O(N) 시간에 동작합니다.

• 공간 복잡도: O(N)

  • Counter 객체: 최대 26개 키 저장이므로 O(1)
  • answer 리스트 및 tmp_reverse: 결과 문자열 길이 N을 저장하므로 O(N)
  • 최종 문자열 생성: O(N)
  • 전체적으로 O(N) 공간을 사용합니다.

---

핵심 포인트

1. 팰린드롬의 대칭성 활용: 팰린드롬은 왼쪽 절반과 오른쪽 절반이 대칭이므로, 왼쪽 절반만 사전순으로 최소화하면 전체 문자열이 최소가 됩니다.
2. 사전순 정렬의 그리디 적용: 문자를 'a'부터 'z' 순으로 정렬하여 왼쪽 절반을 채우면, 가장 앞쪽 위치에 가장 작은 문자가 오도록 보장됩니다.
3. 홀수 문자의 유일한 중앙 배치: 팰린드롬 조건상 홀수 개 문자는 최대 1개만 존재하며, 이는 무조건 정중앙에 위치해야 합니다. 정렬 과정에서 자연스럽게 처리됩니다.

풀이 코드

from collections import Counter

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        count = Counter(s)

        c = sorted(count.items())
        answer = []
        mid = ""

        tmp_y = 0
        for x,y in c:
            for i in range(y//2):
                answer.append(x)

            if y % 2 == 1:
                mid = x

        tmp_reverse = answer[::-1]
        if mid:
            answer.append(mid)

        return ''.join(answer + tmp_reverse)