문자열 s가 주어졌을 때, 해당 문자열의 문자들을 재배열하여 회문(palindrome)을 만들 수 있는지 확인하는 문제를 살펴보겠습니다.
예를 들어, 입력이 s = "raaecrc"라면 문자들을 재배열하여 "racecar"라는 회문을 만들 수 있으므로 결과는 True가 됩니다.
접근 방법
회문의 핵심 성질을 활용하면 문제를 간단히 해결할 수 있습니다. 회문이 성립하려면 다음 두 조건 중 하나를 만족해야 합니다.
- 모든 문자가 짝수 번 나타나는 경우 (짝수 길이 회문)
- 단 하나의 문자만 홀수 번 나타나고, 나머지 문자는 모두 짝수 번 나타나는 경우 (홀수 길이 회문)
즉, 홀수 번 나타나는 문자가 2개 이상 존재한다면 어떻게 재배열하더라도 회문을 만들 수 없습니다.
이 원리를 바탕으로 다음 단계로 문제를 해결합니다.
- freq := 문자열 s의 각 문자와 빈도수를 저장하는 맵 생성
- odd_count := 0 (홀수 빈도를 가진 문자의 개수)
- freq의 모든 값 i에 대해 반복:
- i가 홀수이면 odd_count를 1 증가
- odd_count가 1보다 크면 False 반환
- 반복이 정상적으로 끝나면 True 반환
구현 예제
from collections import defaultdict
def solve(st):
freq = defaultdict(int)
for char in st:
freq[char] += 1
odd_count = 0
for i in freq.values():
if i % 2 == 1:
odd_count = odd_count + 1
if odd_count > 1:
return False
return True
s = "raaecrc"
print(solve(s))입력
"raaecrc"
출력
True
시간 복잡도 분석
이 알고리즘은 문자열을 한 번 순회하여 각 문자의 빈도수를 계산한 뒤, 빈도수 맵을 다시 한 번 순회합니다. 따라서 전체 시간 복잡도는 O(n)이며, 여기서 n은 문자열의 길이입니다. 공간 복잡도는 서로 다른 문자의 개수 k에 비례하여 O(k)입니다.