[백준, C++] 20437 - 문자열 게임 2

https://www.acmicpc.net/problem/20437

20437번: 문자열 게임 2

 

문제 분석

문제를 보고 이건 어떤 식으로 풀어야겠구나 (가령 어떤 알고리즘을 사용해야겠구나 !) 라는 생각이 안 들었다. 뭐라 해야하지 ... 어떻게 풀어야할지도 모를만큼 어려웠다는 뜻이 아니고, 이게 뭔가 특별한 풀이가 필요한가 ? 라는 생각이 들었던 ... 그런 문제이다. 다 풀고나서 문제의 알고리즘 분류를 봤는데, '문자열' 과 '슬라이딩 윈도우' 라고 한다. 음 ... 내가 푼 방식이 슬라이딩 윈도우 개념을 사용하긴 하는데, 딱히 '슬라이딩 윈도우를 써서 풀면 되겠군 !' 이라고 생각하고 접근한 것은 아니었다.

 

내가 생각한 문제 접근법은 이렇다.

 

먼저 행을 26개 가지는(a ~ z 26개) 2차원 벡터(vector<int> vec[26];)를 만들었다. 이 벡터의 행(row)은 알파벳 각각에 해당한다(a = 0, ..., z = 25). 그리고 이 2차원 벡터의 열(column)이 의미하는 것은, 가령 vec[0][col]이 의미하는 것은 문자열에서 알파벳 a가 col + 1번째로 등장한 인덱스를 의미한다.

 

말로 설명하니 제법 어려울 수 있다. 그러니 예시와 함께 보자. 예시 문자열을 happy 라고 해보겠다.

 

1. h

h를 인덱스화하면 a b c d e / f g h, index 7에 해당한다. 따라서 vec[7].push_back(0)을 해준다. 이렇게 되면, vec[7][0]에 0이 할당된다. 이를 해석해보면, "알파벳 'h'(row = 7)가 1번째(col = 0)로 등장한 위치는 0번 index이다" 가 된다.

 

2. a

a를 인덱스화하면 a, index 0에 해당한다. 따라서 vec[0].push_back(1)을 해준다. 이렇게 되면, vec[0][0]에 1이 할당된다. 이를 해석해보면, "알파벳 'a'(row = 0)가 1번째(col = 0)로 등장한 위치는 1번 index이다." 가 된다.

 

3. p

p를 인덱스화하면 a b c d e / f g h i j / k l m n o / p, index 15에 해당한다. 따라서 vec[15].push_back(2)를 해준다. 이렇게 되면, vec[15][0]에 2가 할당된다. 이를 해석해보면, "알파벳 'p'(row = 15)가 1번째(col = 0)로 등장한 위치는 2번 index이다." 가 된다.

 

4. p

p를 인덱스화하면 a b c d e / f g h i j / k l m n o / p, index 15에 해당한다. 따라서 vec[15].push_back(3)를 해준다. 이렇게 되면, vec[15][1]에 3이 할당된다. 이를 해석해보면, "알파벳 'p'(row = 15)가 2번째(col = 1)로 등장한 위치는 3번 index이다." 가 된다.

 

5. y

y를 인덱스화하면 a b c d e / f g h i j / k l m n o / p q r s t / u v w x y, index 24에 해당한다. 따라서 vec[24].push_back(4)를 해준다. 이렇게 되면 vec[24][0]에 4가 할당된다. 이를 해석해보면, "알파벳 'y'(row = 24)가 1번째(col = 0)로 등장한 위치는 4번 index이다" 가 된다.

 

이처럼, 우리는 입력으로 주어진 문자열에 대해 이렇게 2차원 벡터에 정보를 저장할 것이다. row로 '문자' 에 대한 접근을, col로 '등장 순서' 에 대한 접근을 함으로써 어떤 문자가 몇 번째로 등장한 그 위치를 2차원 벡터에 저장하는 것이다.

 

그렇다면 이를 어떻게 문제 해결에 활용할 수 있을까 ? 문제에서 우리가 구해야 하는 것은 아래 두 가지이다.

 

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

 

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

 

3번이 말하고자 하는 것은 특정 문자를 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구하는 것이다. 근데 이는 사실 4번에서 구해야 할 연속 문자열과 조금 비슷하다. 바로 '문자열의 첫 번째와 마지막 글자가 해당 문자로 같다' 는 것이다. 이게 가능한 이유는, 어떤 문자를 K개 포함하면서 가장 짧은 연속 문자열이려면 처음과 끝이 그 '어떤 문자' 여야 가장 짧기 때문이다.

 

슬슬 코드로 봐보자.

 

코드

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int t;
string w;
int k;
vector<int> vec[26];
int answer3, answer4;

void initialize();
void getInput();
void solve();
void printResult();

int toIndex(char);

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> t;
    while (t--) {
        initialize();
        getInput();
        solve();
        printResult();
    }

    return 0;
}

void initialize() {
    for (int i = 0; i < 26; i++) {
        vec[i].clear();
    }
    answer3 = 10001;
    answer4 = -1;
}

void getInput() {
    cin >> w;
    cin >> k;
}

void solve() {
    for (int i = 0; i < w.length(); i++) {
        char c = w[i];
        vec[toIndex(c)].push_back(i);

        // 3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이 구하기
        if (vec[toIndex(c)].size() >= k) {
            int vecSize = vec[toIndex(c)].size();
            int lastIndex = vec[toIndex(c)][vecSize - 1];
            int firstIndex = vec[toIndex(c)][vecSize - k];
            answer3 = min(answer3, lastIndex - firstIndex + 1);
        }

        // 4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이 구하기
        if (vec[toIndex(c)].size() >= k) {
            int vecSize = vec[toIndex(c)].size();
            int lastIndex = vec[toIndex(c)][vecSize - 1];
            int firstIndex = vec[toIndex(c)][vecSize - k];
            answer4 = max(answer4, lastIndex - firstIndex + 1);
        }
    }
}

void printResult() {
    if (answer3 == 10001 || answer4 == -1) {
        cout << "-1\n";
    } else {
        cout << answer3 << " " << answer4 << "\n";
    }
}

int toIndex(char c) {
    return (int)(c - 'a');
}

 

코드 설명

문자열의 각 문자를 읽는다(char c = w[i];). 그리고 문자 c를 인덱스화하여, 2차원 벡터에 문자 c가 등장한 인덱스를 저장한다. 그런데 벡터에 push_back을 하면서 해당 문자 c가 지금껏 K개 이상 등장했다면, 문자열의 부분 문자열을 찾는 작업을 시작하는 것이다.

 

어떤 문자 c가 가장 마지막으로 등장한 인덱스는 당연히 vec[toIndex(c)][vec[toIndex(c)].size() - 1]일 것이다. 그리고 어떤 문자 c가 최근 K번째로 등장한 인덱스는 vec[toIndex(c)][vec[toIndex(c)].size() - k]일 것이다. 이 두 인덱스의 차이를 통해 우리는 부분 문자열의 길이를 알아낼 수 있다. 문제에 나온 진행 방식 3번은 그 길이의 최솟값을, 4번은 그 길이의 최댓값을 원하는 것이므로 적절히 min(), max()를 사용해 답을 구할 수 있다.