백준 20437번 문자열 게임2 (C++)

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

20437번: 문자열 게임 2

문제 요약

 

1. 테스트 케이스 t개 만큼 문자열 w와 양의 정수 k가 주어집니다.

2. 문자열 w에서 어떤 문자를 정확히 k개 포함하고, 가장 짧은 연속 문자열의 길이를 구하세요.

3. 문자열 w에서 어떤 문자를 정확히 k개 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구하세요.

 

핵심 포인트

 

슬라이딩 윈도우 기법을 활용하면 됩니다.

하지만 투 포인터 방법을 기반으로 슬라이딩 윈도우를 구현하지 않아도 정답을 구할수 있습니다.

 

문제 풀이

 

1. 필요한 변수들을 선언하고 값을 입력받습니다.

이때 ans1은 어떤 문자를 k개 포함한 가장 짧은 문자열이며,

ans2는 어떤 문자 k를 포함하여 문자의 시작과 끝이 해당 문자인 가장 긴 문자열입니다.

ans1은 MAX로 초기화하고, ans2는 0으로 초기화합니다.

    int t; 
    cin >> t;
    while(t--){
        int k;
        ans1 = MAX, ans2 = 0;
        string s;
        cin >> s;
        cin >> k;
        find(s,k); // find함수로 정답을 구합니다.
        if(ans1==MAX) cout << -1 << "\n";
        else cout << ans1 << " " << ans2 << "\n";
    }

find라는 void함수를 별도로 구현해 정답을 구합니다.

 

2. find함수 전반부입니다. 이해를 돕기 위해 2번에 나누어 설명하겠습니다.

void find(string s, int k){
    int arr[26] ={0,}, se[26] = {0,}; // 1
    for(int i=0; i<26; i++) se[i] = -1; // 2
    int pos = 0, temp = 0, len = 0;
    for(int i=0; i<s.size(); i++){ // 3
        pos = s[i]-'a'; // 4
        arr[pos]++; // 5
        if(arr[pos]==k){
            if(se[pos]==-1){
                temp = s.find(s[i]);
                se[pos] = temp;
                len = (i-se[pos])+1;
                if(ans1>len) ans1 = len;
                if(ans2<len) ans2 = len;
            }
            else{
                temp = s.find(s[i],se[pos]+1);
                se[pos] = temp;
                len = (i-se[pos])+1;
                if(ans1>len) ans1 = len;
                if(ans2<len) ans2 = len;
            }
            arr[pos]--;
        }
    }
}

(1) arr는 a~z까지의 알파벳이 사용된 횟수를 저장할 배열입니다.

se는 a~z까지의 알파벳이 처음 사용된 위치를 저장할 배열입니다.

(2) 배열은 0부터 시작하므로, 필요한 알파벳이 0번째에 위치할 수 있습니다. 그러므로 se배열은 -1로 초기화해줍니다.

(3) i는 0부터 s의 사이즈-1까지 for문을 돌립니다.

(4) 만약 'a'-'a'를 하면 0입니다. 'b'-'a'를 하면 98-97, 즉, 1이 나옵니다. 이런 원리를 이용하여 s[i]-'a'를 활용해 현재 위치의 알파벳의 자리수를 저장합니다.

(5) 해당 알파벳이 사용된 횟수를 +1해줍니다.

 

3. 다음은 find함수의 후반부입니다.

void find(string s, int k){
    int arr[26] ={0,}, se[26] = {0,};
    for(int i=0; i<26; i++) se[i] = -1;
    int pos = 0, temp = 0, len = 0;
    for(int i=0; i<s.size(); i++){
        pos = s[i]-'a';
        arr[pos]++;
        if(arr[pos]==k){
            if(se[pos]==-1){ // 1
                temp = s.find(s[i]); // 2
                se[pos] = temp; // 3
                len = (i-se[pos])+1; // 4
                if(ans1>len) ans1 = len; // 5
                if(ans2<len) ans2 = len;
            }
            else{
                temp = s.find(s[i],se[pos]+1); // 6
                se[pos] = temp; // 7
                len = (i-se[pos])+1; // 8
                if(ans1>len) ans1 = len;
                if(ans2<len) ans2 = len;
            }
            arr[pos]--; // 9
        }
    }
}

만약 arr[pos]의 갯수가 k개일 경우

(1) se[pos]가 -1이라면, 최초로 해당 알파벳이 k개가 나왔다는 뜻이됩니다.

(2) 문자열 s에서 s[i]의 위치를 찾습니다. 참고로 find함수는 대상이 여러개일 경우 가장 첫 번째로 나온 대상의 위치를 반환합니다.

(3) se[pos]에 temp를 저장합니다. 이제 se[pos]에는 해당 문자가 첫 번째로 사용된 자리를 저장한 셈입니다.

(4) (현재 위치 - se[pos])+1을 구하여 문자열의 길이를 구합니다.

(5) 위에서 구한 문자열의 길이가 2개의 정답을 구하는 조건을 만족할 경우 각각 업데이트를 해줍니다.

(6) 반대로 se[pos]가 -1이 아니라면, 최초로 해당 알파벳이 k개 나온 경우가 아니라는 뜻이됩니다.

문자열 s에서 s[i]의 위치를 찾는것은 동일하지만, 여기에 조건이 하나 붙습니다. se[pos]+1의 위치부터 해당 문자를 찾는 것입니다.

이렇게 해서 이전에 찾았던 해당 문자의 최초의 위치보다 바로 그 다음에 위치한 해당 문자의 자리를 찾을 수 있습니다.

(7) se[pos]에 temp를 업데이를 합니다. 이제 se[pos]에 해당 문자가 새롭게 첫 번째로 사용된 자리를 저장한 셈입니다.

(8) 나머지는 위에서 설명한 것과 동일하므로 생략합니다.

(9) 이렇게 arr[pos]가 k개인 경우를 찾았을 경우, arr[pos]를 -1해줍니다. 계속해서 정확히 k개를 만족하는 어떤 문자열의 길이를 찾아야하기 때문입니다.

 

4. 다시 main으로 돌아옵니다.

    int t; 
    cin >> t;
    while(t--){
        int k;
        ans1 = MAX, ans2 = 0;
        string s;
        cin >> s;
        cin >> k;
        find(s,k);
        if(ans1==MAX) cout << -1 << "\n"; // 1
        else cout << ans1 << " " << ans2 << "\n"; // 2
    }
    return 0;

find함수를 통해 ans1과 ans2를 구했습니다.

(1) 만약 ans1이 MAX일 경우, 정답을 구하는데 실패했다는 뜻이므로 -1을 출력합니다.

(2) 그렇지 않을 경우 정답을 출력합니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX 987654321
using namespace std;

int ans1, ans2;

void find(string s, int k){
    int arr[26] ={0,}, se[26] = {0,};
    for(int i=0; i<26; i++) se[i] = -1;
    int pos = 0, temp = 0, len = 0;
    for(int i=0; i<s.size(); i++){
        pos = s[i]-'a';
        arr[pos]++;
        if(arr[pos]==k){
            if(se[pos]==-1){
                temp = s.find(s[i]);
                se[pos] = temp;
                len = (i-se[pos])+1;
                if(ans1>len) ans1 = len;
                if(ans2<len) ans2 = len;
            }
            else{
                temp = s.find(s[i],se[pos]+1);
                se[pos] = temp;
                len = (i-se[pos])+1;
                if(ans1>len) ans1 = len;
                if(ans2<len) ans2 = len;
            }
            arr[pos]--;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; 
    cin >> t;
    while(t--){
        int k;
        ans1 = MAX, ans2 = 0;
        string s;
        cin >> s;
        cin >> k;
        find(s,k);
        if(ans1==MAX) cout << -1 << "\n";
        else cout << ans1 << " " << ans2 << "\n";
    }
    return 0;
}