문제 소개
소문자 알파벳으로 이루어진 문자열 s가 주어졌을 때, 어떤 한 문자의 등장 횟수가 나머지 모든 문자의 등장 횟수를 합친 값보다 큰 가장 짧은 부분 문자열(최소 길이 2)의 길이를 구하는 것이 목표입니다. 만약 조건을 만족하는 부분 문자열이 하나도 없다면 -1을 반환해야 합니다.
예를 들어 입력이 "abbbcde"라면 출력은 2입니다. 부분 문자열 "bb"가 최소 길이를 가지며, 그 안에서 'b'가 다른 문자들보다 많이 등장하기 때문입니다.
접근 방법
이 문제의 핵심 통찰은 정답이 될 수 있는 길이는 2 또는 3뿐이라는 점입니다.
- 길이 2인 경우: 인접한 두 문자가 서로 같다면(예: "bb") 해당 문자가 2번 등장하므로 곧바로 조건을 만족합니다.
- 길이 3인 경우: 첫 번째 문자와 세 번째 문자가 같다면(예: "aba") 해당 문자가 2번, 나머지 문자가 1번 등장하여 2 > 1이므로 조건을 만족합니다.
- 반면 문자열 어디에도 거리 1 또는 2만큼 떨어진 동일한 문자 쌍이 존재하지 않는다면, 어떤 부분 문자열에서도 특정 문자가 과반을 넘길 수 없으므로 정답은 -1이 됩니다.
전체 알고리즘은 다음 단계로 진행됩니다.
- 빈도 배열 cnt를 입력받아 "최대 빈도가 나머지 빈도의 합보다 큰지"를 판별하는 함수 ok()를 정의합니다.
- total := 0, maxVal := 0으로 초기화합니다.
- cnt의 각 원소 it에 대해 total에 값을 누적하고, maxVal을 현재까지의 최댓값으로 갱신합니다.
- maxVal > (total - maxVal)이면 true를 반환합니다.
- 메인 로직(solve 함수)에서는 아래를 수행합니다.
- n := 문자열 s의 길이로 설정합니다.
- ret := INF(무한대)로 초기화합니다.
- i를 0부터 n-1까지 1씩 증가시키며 반복합니다.
- i + 1 < n이고 s[i] == s[i + 1]이면 즉시 2를 반환합니다.
- 그렇지 않고 i + 2 < n이고 s[i] == s[i + 2]라면 ret := 3으로 설정합니다.
- 반복이 끝난 후 ret가 여전히 INF라면 -1을, 그렇지 않으면 ret를 반환합니다.
C++ 구현 예제
아래 코드를 통해 풀이 과정을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(vector<int>& cnt){
int total = 0;
int maxVal = 0;
for(auto& it : cnt){
total += it;
maxVal = max(maxVal, it);
}
return maxVal > (total - maxVal);
}
int solve(string s) {
int n = s.size();
int ret = INT_MAX;
for(int i = 0; i < n; i++){
if(i + 1 < n && s[i] == s[i + 1]){
return 2;
}else if(i + 2 < n && s[i] == s[i + 2]){
ret = 3;
}
}
return ret == INT_MAX ? -1 : ret;
}
};
int main(){
Solution ob;
cout << (ob.solve("abbbcde"));
}
입력
"abbbcde"
출력
2
복잡도 분석 및 마무리
이 풀이는 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 공간은 상수만 사용하므로 공간 복잡도는 O(1)입니다. 인접한 두 문자 또는 한 칸 건너 있는 두 문자의 일치 여부만 확인하면 되기 때문에 로직이 단순하면서도 매우 효율적이며, 길이가 긴 문자열에서도 빠르게 동작합니다.