GSHS와 SSHS의 개수 차이를 최대 구간 합으로 계산하기

문자열에서 GSHS와 SSHS를 따로 세는 것보다, 각 시작 위치를 점수로 바꾸면 두 패턴의 개수 차이를 한 번에 다룰 수 있다. SSHS는 +1, GSHS는 -1, 나머지는 0으로 놓는 방식이다.

이 코드는 처음에 GSHS의 시작 위치를 누적하다가, 두 패턴의 차이가 가장 큰 연속 구간을 찾는 쪽으로 바뀌었다. 다만 최종 출력은 최대 개수 차이뿐이므로, 이것이 문제에서 요구하는 답과 일치하는지는 조건을 확인해야 한다.

GSHS의 시작 위치 세기

처음에는 각 위치에서 네 글자가 GSHS인지 확인하고 cntG[i]를 늘렸다. 이 단계의 코드에는 두 가지 문제가 있었다.

vector<int> cntG;
for (int i = 0; i < s.size() - 3; i++) {
    if (s[i] == 'G' && s[i + 1] == 'S' && s[i + 2] = 'H' &&
        s[i + 3] == 'S')
        cntG[i]++;
}

cntG가 빈 벡터이므로 인덱스로 접근할 공간이 없다. 또 s[i + 2] = 'H'는 비교가 아니라 대입 연산자를 쓴 오타이다. 이후 비교는 ==로 고치고 벡터는 cntG(N, 0)으로 초기화했다. 여기에 이전 위치의 값을 더하면서 GSHS가 시작된 횟수를 누적했다.

공통 접미사로 두 패턴 분리하기

GSHS만 세어서는 SSHS와의 차이를 구할 수 없다. 수정 중에는 잠시 조건문 밖에서 cntG[i]++를 실행해 모든 위치를 세는 상태가 생겼지만, 곧 공통 접미사 SHS를 먼저 확인하고 첫 글자에 따라 카운트를 나누었다.

if (s[i + 1] == 'S' && s[i + 2] == 'H' && s[i + 3] == 'S') {
    if (s[i] == 'G') cntG[i]++;
    if (s[i] == 'S') cntS[i]++;
}

따라서 한 시작 위치에서 cntS가 늘면 점수는 +1, cntG가 늘면 -1이다. 나머지 위치의 점수는 0이다. 이 점수들의 구간 합은 해당 구간에서 시작하는 SSHS의 개수에서 GSHS의 개수를 뺀 값이 된다.

누적 차이에서 최대 구간 합으로

처음 추가한 최댓값 갱신은 이전 값을 더하기 전에 이루어졌다. 이 순서에서는 현재 위치의 차이만 비교한다. 이후 두 배열을 모두 누적하고 나서 ans를 갱신하도록 순서를 바꾸었다. 이어 GSHS의 누적 개수가 더 많아 차이가 음수가 되면 두 값을 0으로 초기화했다.

if (i > 0) {
    cntG[i] += cntG[i - 1];
    cntS[i] += cntS[i - 1];
}

if (cntG[i] > cntS[i]) cntG[i] = cntS[i] = 0;
ans = max(ans, cntS[i] - cntG[i]);

음수인 구간을 뒤의 구간에 붙이면 합이 오히려 작아진다. 따라서 그 구간은 버리고 다음 위치부터 다시 시작하는 편이 낫다. 이 초기화가 들어간 뒤의 배열 값은 문자열 처음부터의 단순 누적 개수가 아니라, 마지막 초기화 이후 이어 온 구간의 개수이다.

예를 들어 GSHSSHS에서는 0번 위치의 GSHS가 -1, 3번 위치의 SSHS가 +1이다. 앞의 음수 점수를 버리면 최대 차이는 1이다. ans를 0으로 시작하므로 빈 구간도 허용한 최대 구간 합을 구하게 된다.

마지막 시작 위치와 짧은 문자열

반복 조건은 한때 i < s.size() - 4로 바뀌었다가 i < s.size() - 3으로 돌아왔다. 네 글자를 확인할 때 마지막 시작 위치는 s.size() - 4이므로, 그 위치까지 포함하려면 후자의 조건이 필요하다. 특히 길이가 4인 문자열도 한 번 검사해야 한다.

최종 코드에는 길이가 4보다 작을 때 0을 출력하고 종료하는 분기도 추가되었다. 검사할 네 글자가 없을 뿐 아니라, 부호 없는 size()에서 3을 빼는 과정의 언더플로도 피할 수 있다.

문자열 길이 N이 입력된 문자열의 길이와 일치한다고 보면 시간과 공간은 모두 O(N)이다. 이 전제는 벡터를 N 크기로 만들고 문자열의 길이를 기준으로 순회하는 코드에 필요하다.

마지막으로 이 구현은 전체 GSHS 개수를 더하지 않고 최대 차이만 출력한다. 예를 들어 입력 문자열이 GSHS이면 출력은 0이다. 따라서 이 값 자체가 요구되는 답인지, 아니면 별도의 기준값을 더해야 하는지는 문제 조건과 대조해야 한다.