[BOJ] 24525: SKK 문자열 (C/C++)

문제 24525번: SKK 문자열

포함된 K의 개수가 S의 개수의 정확히 $2$배이면서, S와 K가 적어도 한 번은 등장하는 문자열을 SKK 문자열이라고 한다.

SKK 문자열은 S, K 말고도 다른 알파벳 또한 포함할 수 있다.

알파벳 대문자로만 이루어진 문자열 $S$가 주어질 때, $S$의 부분 문자열 중 길이가 가장 긴 SKK 문자열을 찾는 프로그램을 작성하라.

입력

첫째 줄에 길이가 $1$이상 $100,000$ 이하인 알파벳 대문자로만 이루어진 문자열 $S$가 주어진다.

각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다.

출력

$S$의 부분 문자열 중 길이가 가장 긴 SKK 문자열의 길이를 출력한다. 만약 그러한 문자열이 없으면 -1을 출력한다.

문제분석

문제 요구사항

• SKK문자열을 찾아야 한다.
  • [0~i]의 범위를 가지는 부분 문자열 s내의 ‘S’와 ‘K’의 갯수를 기반으로하는 Index를 사용하는 Vector를 만든다.

각 부분 문자열의 ‘S’와 ‘K’의 갯수를 기반으로 한 Index를 사용하는 Vector를 활용하여 문제를 해결한다.

구현

[0~i]의 범위를 가지는 부분 문자열 s의 ‘S’와 ‘K’의 갯수를 저장하는 cnt_skk라는 Vector를 선언 한 후, i=s.length()-1 가 될때 까지 cnt_skk의 값을 채워 넣는다.
그 후, ‘S’의 갯수와 ‘K’의 갯수를 기반으로 index를 사용하는 skk_index라는 Vector를 만든 후, 해당 Vector에 요소에 처음 접근하는 부분 문자열의 i를 저장시킨다.
그 후, skk_index를 활용하여 최대 SKK문자열의 길이를 구한다.

증명

skk_index[i]에 접근하는 부분문자열이 있다고 가정하자.
이때 skk_index[i]==-1 이라면 해당 문자열이 처음 skk_index[i]에 접근했음으로, 해당 문자열의 길이를 skk_index에 저장 시킨다.

skk_index[i]!=-1 이라면, 해당 문자열이 skk_index[i]에 처음 접근하는 부문 문자열이 아님으로, cnt_skk를 활용하여 현재 부분 문자열과 skk_index[i]가 가르키는 부분 문자열 사이에 ‘S’혹은 ‘K’가 있는지 판별하기 위하여 cnt_skk[현재 부분 문자열 index]-cnt_skk[이전 부분 문자열 index]를 하여 만들어진 SKK문자열이 valid한 문자열인지 판별한다.
이 과정을 통하여 조건을 만족하는 최장 부분문자열을 찾을 수 있다.

코드

#include <iostream>
#include <string>
#include <utility>
#include <vector>

const std::pair<int, int> operator-(const std::pair<int, int>& lp,
                                    const std::pair<int, int>& rp) {
  return std::pair<int, int>(lp.first - rp.first, lp.second - rp.second);
}

const bool operator!=(const std::pair<int, int>& lp,
                      const std::pair<int, int>& rp) {
  return lp.first != rp.first || lp.second != rp.second;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);

  std::string str;
  str.reserve(100'000);
  std::cin >> str;

  /*std::pair.first = count_s, std::pair.second = count_k*/
  std::vector<std::pair<int, int>> cnt_skk(str.length() + 1);
  /*skk_index[i] : i= 2*cnt_s-cnt_k*/
  std::vector<int> skk_index(str.length() * 4 + 1, -1);
  skk_index[2 * str.length()] = 0;
  int ans = -1;
  for (int i = 1; i < cnt_skk.size(); ++i) {
    cnt_skk[i] = cnt_skk[i - 1];

    if (str[i - 1] == 'S') {
      cnt_skk[i].first++;
    }
    if (str[i - 1] == 'K') {
      cnt_skk[i].second++;
    }

    const int index =
        2 * cnt_skk[i].first - cnt_skk[i].second + 2 * str.length();
    if (skk_index[index] == -1) {
      skk_index[index] = i;
    } else {
      if ((cnt_skk[i] - cnt_skk[skk_index[index]]).first != 0) {
        ans = std::max(ans, i - skk_index[index]);
      }
    }
  }

  std::cout << ans;

  return 0;
}