[코드포스 Practice9] E. RGB Substring (hard version)

The only difference between easy and hard versions is the size of the input.
easy 와 hard 버젼의 유일한 차이는 입력 크기이다. 

You are given a string s consisting of n characters, each character is 'R', 'G' or 'B'.

너는 각 문자가 RGB로 이루어져 있고 n개의 문자로 구성된 문자열 s가 주어졌다.

You are also given an integer k. Your task is to change the minimum number of characters in the initial string s so that after the changes there will be a string of length k that is a substring of s, and is also a substring of the infinite string "RGBRGBRGB ...".

또한 정수 k도 주어진다. 너가 할 일은 처음 문자열 s를 문자의 개수를 최소한으로 변경하는 것이다. 그래서 변경 후에 s의 부분 문자열이고 또한 무한대 문자열인 RGBRGB...의 부분 문자열인 길이가 k인 문자열이 있을 것이다. 

A string a is a substring of string b if there exists a positive integer i such that a1=bi, a2=bi+1, a3=bi+2, ..., a|a|=bi+|a|−1. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

만약 ~~~이런 조건을 만족하는 양수 i가 존재한다면 문자열 a는 문자열 b의 부분 문자열이다. 예를 들어 문자열 "GBRG", "B", "BR"은 무한 문자열인 "RGBRGBRGB ..."의 부분 문자열이고, "GR", "RGR" and "GGG"는 아니다.

 

You have to answer q independent queries.

서로 다른 q개의 질문에 답해야 한다.

Input
The first line of the input contains one integer q (1≤q≤2⋅10^5) — the number of queries. Then q queries follow.

입력의 첫 줄에는 하나의 정수 q를 포함하고 있다. -- 질문의 개수이다. 그리고 q개의 문제가 따라온다.

The first line of the query contains two integers n and k (1≤k≤n≤2⋅105) — the length of the string s and the length of the substring.

문제의 첫번째 줄은 두 개의 정수 n과 k를 포함한다. -- 문자열 s의 길이이고 부분 문자열의 길이이다.

The second line of the query contains a string s consisting of n characters 'R', 'G' and 'B'.

문제의 두 번째 줄은 'R', 'G' 'B' n개의 문자로 구성된 문자열 s를 포함하고 있다. 

It is guaranteed that the sum of n over all queries does not exceed 2⋅105 (∑n≤2⋅105).

모든 문제의 n의 합은 2*10^5를 초과하지 않음이 보장된다

Output
For each query print one integer — the minimum number of characters you need to change in the initial string s so that after changing there will be a substring of length k in s that is also a substring of the infinite string "RGBRGBRGB ...".

각 질문에 대해 정수를 하나씩 출력해라 -- 처음 문자열 s에서 너가 바꿔야 할 문자의 최소 개수이다. 무한 문자열인 "RGBRGBRGB ..."의 부분 문자열이며 바꾼 이후 길이가 k인 부분 문자열이 있을 것이다. (아 이 문장 너무 길고 어떻게 번역해야할지 모르겠음)

 

---

 

딱 봐도 시간복잡도 신경써야 할 문제..

남은 시간 동안 못 풀 것 같아서 문제 읽다가 고이 접어놨다.

 

 

근데 다시 봐도 모르겠음ㅠㅠ

어떻게 해야 logN번 이내로 돌지???

내가 아는 O(logN)은 약수 구하는 거랑 소수 구하는 거랑 파라메트릭 서치 뿐인데 파라메트릭으로 안 풀리지 않나??? 

 

 

ㅋㅋㅋㅋ알고보니 조건이 하나 더 있었다. 어쩐지 이상하다 했었다!

n의 합이 20만을 넘지 않아서 입력받고 배열 순회 한다고 터지지는 않음

 

 

 

 

O(N)이면 돼서 그때부터 맘편히 풀었다.

 

전에 k-dominant 문제 풀 때 처럼 투포인터인데 한 칸씩 움직이면서 맨 앞뒤 값만 변경시켰다. 

값 비교하는 건 RGB 문자열 하나씩 가리키면서 비교했음. 처음에는 문자열 길이만큼 RGB를 만들어서 비교할까 했는데 어짜피 계속 RGB반복될꺼 굳이?라는 생각 들어서 이렇게 했다. 

 

 

 

이건 내용 그대로 코드 짠 거

처음 생각한 게 이거라 실제로 짠 건 고쳐서 짰다. (왜냐면 저건 안 돌아가기 때문에)

 

아, 여기서 min값을 잘못 설정해서 조금 헤맸다. 

사진 보면 같은거 개수를 구했는데 문제에서 구하는 건 바꿔야 하는 문자 개수이다. 그래서 k - count 로 바꿨음.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long int;

string RGB = "RGB";

int main(){
    int q;
    scanf("%d", &q);
    
    for(int i = 0; i < q; i++) {
        int n, k;
        scanf("%d %d", &n, &k);
        string s;
        cin >> s;
        int min = s.size();
        
        for(int j = 0; j < 3; j++){
            int l = 0, r = 0;
            int c = j;
            int count = 0;
            
            for(int i = 0; i < k; c++,i++){
                if(s[i] == RGB[c%3])
                    count++;
            }
            if(k-count < min)
                min = k-count;
            
            for(int r = k; r < n; r++, c++){
                if(s[r] == RGB[c%3])
                    count++;
                if(s[r-k] == RGB[(c-k)%3])
                    count--;
                if(k-count < min)
                    min = k-count;
            }
        }
        cout << min << endl;
    }
    
    return 0;
}

 

 

 

예헤이