[BOJ 24525] 백준 24525번 - SKK 문자열

		2022 성균관대학교 프로그래밍 경진대회 Open Contest 풀이
A		[BOJ 24523] 내 뒤에 나와 다른 수
B		[BOJ 24524] 아름다운 문자열
C		[BOJ 24525] SKK 문자열
D		[BOJ 24526] 전화 돌리기
E		[BOJ 24527] 이상한 나라의 갈톤보드

1. 문제

$24525$. SKK 문자열 (2022 성균관대학교 프로그래밍 경진대회 Open Contest C번)

백준 24525번 - SKK 문자열 (https://www.acmicpc.net/problem/24525)

2. 풀이

$K$의 개수가 $S$의 개수의 두 배가 되어야 하기 때문에, $S$를 $2$로 간주하고 $K$를 $-1$로 간주하면, 구간 합이 $0$이 되는 부분이 $SKK$ 문자열임을 알 수 있다.

구간 합 $A\sim B$가 $0$이라는 것은 $prefix[B] - prefix[A - 1] = 0$과 동일하다. (prefix: 누적합) 따라서 $prefix[A-1]=prefix[B]$로 식을 바꾸어 보면, 어떤 $i$와 $j$ index에서 prefix 값이 같다면, $i+1\sim j$ 구간이 $SKK$ 문자열임을 알 수 있다.

길이가 가장 긴 $SKK$ 문자열을 찾아야 하기 때문에, 각 누적합 값이 처음으로 등장하는 최소 인덱스를 찾는다. 문자열이 전부 $K$일 때 누적합은 $-100,000$이 나오고, 전부 $S$일 때는 $200,000$이 나온다.

따라서 누적합의 범위는 $-100,000\sim 200,000$이고, 이 값이 등장하는 최소 인덱스를 담는 배열을 만든다. (배열은 $-100,000$이 없기 때문에, 전체에 $100,000$을 더해서 $0\sim 300,000$으로 간주한다.)

각 index마다 해당 index의 누적합의 값이 등장하는 최소 인덱스를 토대로 길이를 구할 수 있다. 이때, 이 구간에서 $S$와 $K$가 각각 하나 이상 등장해야 하므로, 이 또한 추가로 확인해 주어야 한다. $s$의 개수, $k$의 개수를 담는 prefix 배열을 만들어서 동일한 방식으로 구간별 $s,\, k$의 개수를 알 수 있다.

3. 채점 결과

4. 회고

.

5. 코드