개발 블로그

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

문제

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

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

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

입력

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

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

출력

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

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

접근 방법

먼저 문제를 풀기 전에 조건의 3번, 4번에 적힌 문장 의미를 잘 이해해야 한다.

3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.

  는 결국 조건 4와 같이 연속 문자열의 양 끝이 그 어떤 문자로 이루어졌을 것이다.

 (W = "baa", K = 2  or W = "aaa", K=2  or W = "abaa", K = 2)

4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

   이 조건은 어떤 문자와 해당 문자가 같으므로, 역시 연속 문자열의 양 끝이 그 어떤 문자로 이루어졌을 것이다.

  (W = "baaabaab", K = 5)

start 인덱스를 정하고, start 인덱스를 기준으로 end 인덱스를 옮겨가면서 완전탐색을 하면 시간초과가 난다.

그래서 W의 모든 문자에 대해서가 아닌,

K개 이상 나온 알파벳을 후보로 정한 후에, 그 후보들에 대해서만 인덱스 검사를 해서 최소와 최대 길이를 구하면 된다.

먼저 예시인 W = "abaaaba", K=3에 대해 살펴보자.

크기가 26인 벡터 배열을 만든다음, W에서 해당 알파벳의 인덱스를 벡터에 저장한다. 

i=0일때의 W[0] = 'a'이므로 a를 의미하는 W[0]-97 = 0을 인덱스로 지정한다.

i=1일때의 W[1] = 'b'이므로 b를 의미하는 W[1] - 97 = 1을 인덱스로 지정한다.

이제 벡터배열을 돌면서 크기가 K이상인 벡터에 대해서만 검사를 진행한다.

문자열에 K개가 포함되야 하므로, 검사는 (벡터크기 - K + 1) 번 진행한다. 즉 j = 0부터 j = vecList[i].size() - K 까지 검사한다. 

또한 K개를 포함하는 연속문자열의 길이를 구하기 위해서는, 

vecList[i][j+K-1] - vecList[i][j] + 1

와 같이 구할 수 있다.

위의 i = 0일 때, 벡터 {0,2,3,4,6}을 예로 들어보면 

3-0 +1 = 4 (aaba)

4-2 +1 = 3 (aaa)

6-3 + 1 = 4 (aaba)

와 같이 구할 수 있다. 

//
//  문자열_BOJ20437_문자열게임2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/09.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
 
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
 
int main(){
    
    int T;
    cin >> T;
    
    vector<int> vecList[26];
 
    for(int test_case = 1; test_case <=T; test_case++){
        string W;
        int K;
        cin >> W >> K;
        
        int mini = 100000;
        int maxi = 0;
        for(int i = 0; i<26; i++) vecList[i].clear();
        for(int i = 0; i<W.length(); i++){
            int num = W[i] - 97;    // 's' = 18
            vecList[num].push_back(i);      //해당 문자의 인덱스를 넣음.
        }
       
        for(int i = 0; i<26; i++){
            int vsize = (int)vecList[i].size();
            if(vsize >= K){ //조건을 만족하는 후보 알파벳들만 고려해서 탐색함으로써 시간 초과 해결.
                for(int j = 0; j<=vsize - K; j++){  //최소 K개를 포함해야 하므로, 만약 vsize=5이고, K=3이면 j=0,1,2까지만 검사하면 됨.
                    mini = min(mini, vecList[i][j+K-1] - vecList[i][j] + 1);
                    maxi = max(maxi, vecList[i][j+K-1] - vecList[i][j] + 1);
                }
            }
        }
        
        if(mini == 100000 || maxi == 0) cout << -1 << "\n";
        else cout << mini << " " << maxi << "\n";
        
    }
    
    return 0;
}