mintchoco

(BOJ5525 IOIOI

Link copied to clipboard

문제 설명

Link copied to clipboard
  • 문자열을 순회하며 특정 패턴을 찾는 문제
  • 문자열 길이가 최대 1,000,000이므로 $O(N^2)$으로 탐색하면 시간초과가 날 것이다.
  • 다행히도 패턴이 간단하여 $O(N)$탐색으로 가능하다
    • 우선 가장 긴 $P_N$문자열을 탐색하고,
    • 해당 문자열에서 n길이의 문자열의 갯수를 확인한다.

문제 풀이

Link copied to clipboard
n, m = int(input()), int(input())
s = str(input().strip())

count = 0
left, right = -1, -1
idx = 0
while True:
    if idx == m:
        count += get_count(n, left, right)
        break
    if left == right:
        if s[idx] == "I":
            left = idx
        idx += 1
    else:
        if idx == m - 1:
            idx += 1
        elif s[idx : idx + 2] == "OI":
            right = idx + 1
            idx += 2
        else:
            count += get_count(n, left, right)
            left = right = idx - 1
print(count)
  • 지금 탐색하는 idx와 탐색하는 $P_N$문자열 시작, 끝을 left, right로 두어 탐색한다.
    • 만약 지금 문자열을 탐색하는 상태가 아니고, I를 만다면 left를 표시한다.
    • 탐색중이고 OI를 만나면 idx, right를 이동하여 문자열을 확장한다.
def get_count(N: int, left: int, right: int) -> int:
    o_count = (right - left) // 2
    if o_count < N:
        return 0
    return o_count - N + 1
  • 특정 길이 문자열의 갯수는,
    • O의 갯수를 먼저 확인하고,
    • 가능한 문자열의 갯수를 반환한다.