두 개의 숫자 n과 k가 주어졌을 때, 오직 'a', 'b', 'c' 세 종류의 문자만으로 구성된 길이 n의 문자열 S를 생성하는 문제를 살펴보겠습니다. 여기서 핵심 조건은 문자열 S 안에 존재하는 회문(palindrome) 부분 문자열 중 가장 긴 것의 길이가 k를 초과하지 않아야 한다는 점입니다.
예를 들어 n = 3, k = 2가 입력으로 주어진 경우를 생각해 봅시다. 이때 가능한 답 중 하나는 "aab"입니다. 문자열의 길이는 3이고, 가장 긴 회문 부분 문자열은 "aa"(길이 2)이므로 k 이하라는 조건을 만족합니다. 물론 "abc"처럼 회문 부분 문자열의 최대 길이가 1에 불과한 다른 정답도 얼마든지 존재할 수 있습니다.
해결 아이디어
이 문제는 의외로 간단한 규칙적 패턴으로 해결할 수 있습니다. 바로 'a', 'b', 'c' 세 문자를 순서대로 순환하며 이어 붙여 "abcabcabc..." 형태의 문자열을 만드는 것입니다.
알고리즘 단계
- 빈 문자열 S를 준비하고 카운터 j를 0으로 초기화합니다.
- i를 0부터 n-1까지 반복하면서 S의 끝에 ('a' + j)에 해당하는 문자를 추가합니다.
- 매 반복마다 j를 (j + 1) % 3으로 갱신하여 'a' → 'b' → 'c' 순서로 순환시킵니다.
- 반복이 끝나면 완성된 문자열 S를 반환합니다.
이 방법이 동작하는 이유
'a', 'b', 'c'가 순환하며 배치되기 때문에 서로 인접한 두 문자는 절대 같아질 수 없습니다. 또한 주기가 3이므로 s[i]와 s[i+2]는 항상 다른 문자가 되어 "aba"처럼 양 끝이 같은 길이 3짜리 회문도 발생하지 않습니다. 그 결과 최장 회문 부분 문자열의 길이는 항상 1로 유지되며, k가 1 이상이기만 하면 어떤 입력에 대해서도 조건을 만족합니다. 시간 복잡도와 공간 복잡도는 모두 O(n)으로 매우 효율적입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
string solve(int n, int k) {
string S = "";
int j = 0;
for (int i = 0; i < n; i++) {
S += j + 'a';
j = (j + 1) % 3;
}
return S;
}
int main() {
int n = 3;
int k = 2;
cout << solve(n, k) << endl;
}실행 결과
입력:
3, 2
출력:
abc
위 코드는 n = 3일 때 "abc"를 출력합니다. 이 문자열에는 길이 2 이상의 회문 부분 문자열이 하나도 없으므로 k = 2 조건을 충분히 만족합니다. 이처럼 세 문자의 단순 순환만으로도 원하는 제약 조건을 손쉽게 달성할 수 있습니다.