문제 개요
문자열 s와 정수 k가 주어졌을 때, s에 있는 모든 문자를 사용하여 k개의 비어 있지 않은 팰린드롬(회문) 문자열을 구성할 수 있는지 확인하는 문제입니다. 즉, 남는 문자 없이 s 전체를 k개의 회문으로 나눌 수 있는지 판단해야 합니다.
예를 들어 입력이 "true"이고 k = 4인 경우, 네 글자를 각각 별도의 한 글자짜리 회문 문자열로 배치하는 것이 유일한 해이므로 결과는 True가 됩니다.
접근 방법
팰린드롬의 핵심 성질을 이용하면 문제를 간단히 해결할 수 있습니다. 팰린드롬에서는 최대 한 개의 문자만 홀수 번 등장할 수 있습니다. 따라서 다음과 같은 논리로 판단합니다.
- 문자열의 길이 n이 k보다 작으면, k개의 비어 있지 않은 문자열을 만들 문자 자체가 부족하므로 false를 반환합니다.
- n이 k와 같다면, 각 문자를 하나씩 분리하면 모두 길이 1의 회문이 되므로 true를 반환합니다.
- 그 외의 경우에는 맵을 사용해 각 문자의 등장 횟수를 계산합니다.
- 홀수 번 등장하는 문자의 개수(odd)를 센 뒤, odd <= k이면 true, 그렇지 않으면 false를 반환합니다.
홀수 빈도 문자가 k개 이하라면, 각 홀수 문자를 서로 다른 회문에 하나씩 배정하고 나머지 짝수 빈도 문자들을 적절히 분배할 수 있기 때문입니다.
알고리즘 단계
- n := s의 길이
- n < k이면 false 반환
- n == k이면 true 반환
- 맵 m을 정의하고 s의 각 문자 c에 대해 m[c]를 1씩 증가
- odd := 0으로 초기화
- m의 각 key-value 쌍 it에 대해 odd += (it의 값 AND 1)
- odd <= k이면 true, 아니면 false 반환
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canConstruct(string s, int k) {
int n = s.size();
if (n < k)
return false;
if (n == k)
return true;
map<char, int> m;
for (char c : s)
m[c]++;
int odd = 0;
for (auto& it : m) {
odd += (it.second & 1);
}
return odd <= k;
}
};
main(){
Solution ob;
cout << (ob.canConstruct("true",4));
}
입력
"true"
출력
1
복잡도 분석
모든 문자를 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 공간 복잡도는 문자 종류에 비례하며, 알파벳 소문자만 있는 경우 사실상 O(1)로 볼 수 있습니다.