BOJ 20437: 문자열 게임 2 (C++)

문제 링크 : https://www.acmicpc.net/problem/20437

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

알파벳 소문자로 이루어진 문자열 $W$가 주어진다.
양의 정수 $K$가 주어진다.
어떤 문자를 정확히 $K$개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
어떤 문자를 정확히 $K$개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 $T$회 진행한다.

입력

문자열 게임의 수 $T$가 주어진다. $(1 ≤ T ≤ 100)$

다음 줄부터 2개의 줄 동안 문자열 $W$와 정수 $K$가 주어진다. $(1 ≤ K ≤ |W| ≤ 10,000) $

출력

$T$개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

풀이

인덱스 전처리

문자별로 인덱스를 전처리한다. 예를 들어, 문자열이 apple 이라면 아래와 같이 저장하면 된다.

char	index
a	0
p	1, 2
l	3
e	4

1
2
3
4


vector<vector<int>> v((int) 'z' + 1);
for (int i = 0; i < s.length(); ++i) {
    v[s[i]].push_back(i);
}

슬라이딩 윈도우 적용

인덱스들은 자연스럽게 정렬이 되어 있을 것이다.

길이가 K인 슬라이딩 윈도우를 적용한다. a부터 z까지 인덱스가 저장된 벡터를 보면서, 문자가 K인 범위의 길이를 구해주자. start는 0부터 시작하고, end는 k-1 부터 시작하면 된다.

문자가 K개 나오는 범위의 길이는 인덱스[end] - 인덱스[start] + 1 로 구할 수 있다.

1
2
3
4
5


for (char c = 'a'; c <= 'z'; ++c) {
    for (int start = 0, end = k - 1; end < v[c].size(); ++end, ++start) {
        int length = v[c][end] - v[c][start] + 1;
    }
}

아래와 같이 Range-based for loop을 사용해도 된다.

1
2
3
4
5


for (auto indexes : v) {
    for (int start = 0, end = k - 1; end < indexes.size(); ++end, ++start) {
        int length = indexes[end] - indexes[start] + 1;
    }
}

정답 출력

최대값과 최소값을 구한 후 출력해 주자. 이 때, min_len이 INT_MAX라는 것은 값을 찾지 못했다는 뜻이므로 -1을 출력한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


int min_len = INT_MAX;
int max_len = INT_MIN;
for (auto indexes : v) {
    for (int start = 0, end = k - 1; end < indexes.size(); ++end, ++start) {
        int length = indexes[end] - indexes[start] + 1;
        min_len = min(min_len, length);
        max_len = max(max_len, length);
    }
}

if (min_len == INT_MAX) {
    cout << -1 << endl;
} else {
    cout << min_len << ' ' << max_len << endl;
}

소스 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s;
    cin >> s;
    int k;
    cin >> k;
    
    vector<vector<int>> v((int) 'z' + 1);
    for (int i = 0; i < s.length(); ++i) {
        v[s[i]].push_back(i);
    }
    
    int min_len = INT_MAX;
    int max_len = INT_MIN;
    for (auto indexes : v) {
        for (int start = 0, end = k - 1; end < indexes.size(); ++end, ++start) {
            int length = indexes[end] - indexes[start] + 1;
            min_len = min(min_len, length);
            max_len = max(max_len, length);
        }
    }
    
    if (min_len == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << min_len << ' ' << max_len << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}