개요
주어진 문자열의 문자들을 임의로 재배열했을 때, 그 결과가 회문(palindrome)이 될 수 있는지 판별하는 문제입니다. 여기서 회문이란 앞에서 읽으나 뒤에서 읽으나 같은 문자열을 의미합니다.
예를 들어 입력 문자열이 s = "aarcrce"라고 가정해 보겠습니다. 이 문자들의 순서를 바꾸면 "racecar"라는 회문을 만들 수 있으므로, 출력은 True가 됩니다.
접근 방식
이 문제를 해결하는 핵심 아이디어는 문자의 등장 빈도에 있습니다.
- 회문이 성립하려면 대칭 구조가 필요합니다.
- 길이가 짝수인 회문이라면 모든 문자가 반드시 짝수 번 나타나야 합니다.
- 길이가 홀수인 회문이라면 정확히 하나의 문자만 홀수 번 나타날 수 있으며(가운데 위치), 나머지는 모두 짝수 번 나타나야 합니다.
따라서 다음과 같은 단계로 문제를 해결할 수 있습니다.
- 크기가 256인 배열을 생성하고 0으로 초기화합니다. (ASCII 문자 전체를 커버하기 위함)
- 문자열을 순회하면서 각 문자의 등장 횟수를 배열에 기록합니다.
- 빈도가 홀수인 문자의 개수(
odd_count)를 셉니다. - 순회 중
odd_count가 1을 초과하면 즉시 False를 반환합니다. - 모든 검사를 통과하면 True를 반환합니다.
구현 예제
size = 256
def solve(s) :
freq = [0] * size
for i in range(0, len(s)) :
freq[ord(s[i])] = freq[ord(s[i])] + 1
odd_count = 0
for i in range(0, size) :
if freq[i] % 2 == 1 :
odd_count = odd_count + 1
if odd_count > 1:
return False
return True
s = "aarcrce"
print(solve(s))입력
"aarcrce"
출력
True
동작 원리 상세 분석
입력 문자열 "aarcrce"의 경우 각 문자의 빈도는 다음과 같습니다.
- 'a' → 2회 (짝수)
- 'r' → 2회 (짝수)
- 'c' → 2회 (짝수)
- 'e' → 1회 (홀수)
홀수 빈도를 가진 문자는 'e' 하나뿐이므로 odd_count = 1이 되고, 조건을 만족하여 True가 반환됩니다. 실제로 이 문자들을 재배열하면 "racecar"와 같은 회문을 만들 수 있습니다.
복잡도 분석
- 시간 복잡도: O(n) — 문자열 길이 n에 비례하여 한 번씩 순회합니다.
- 공간 복잡도: O(1) — 크기가 고정된 256 크기의 배열만 사용하므로 상수 공간입니다.
마무리
이 알고리즘은 해시맵이나 collections.Counter를 활용해서도 동일하게 구현할 수 있으며, 문자 종류가 유니코드 전체로 확장되더라도 자료구조만 교체하면 손쉽게 적용 가능합니다. 회문 관련 문제는 코딩 테스트에서 자주 등장하는 유형이므로, 빈도 기반 접근법을 잘 기억해 두면 다양한 변형 문제에도 유용하게 활용할 수 있습니다.