BOJ 5586 - JOI와 IOI

문제

BOJ 5586 - JOI와 IOI

알파벳 대문자로 이루어진 문자열이 주어진다. 문자열에서 "JOI"와 "IOI"가 각각 몇 번 등장하는지 세어 출력하는 문제다. 부분 문자열은 겹쳐도 별도로 카운트한다.

입력

• 한 줄: 알파벳 대문자 문자열 (길이 ≤ 100)

출력

첫 번째 줄에 "JOI"의 등장 횟수, 두 번째 줄에 "IOI"의 등장 횟수를 출력한다.

예제

풀이

문자열을 슬라이딩 윈도우로 순회하면서 길이 3의 부분 문자열이 "JOI" 또는 "IOI"인지 확인한다.

1. 문자열을 입력받는다.
2. 인덱스 0부터 len(s) - 3까지 순회하며 3글자 구간 s[i:i+3]을 추출한다.
3. 추출한 구간이 "JOI"이면 joi_count를, "IOI"이면 ioi_count를 증가시킨다.
4. 두 카운트를 순서대로 출력한다.

핵심 아이디어: 고정 길이 부분 문자열 탐색은 슬라이딩 윈도우로 O(N) 시간에 처리할 수 있다. 겹치는 경우도 자동으로 처리된다.

코드

import sys
 
s = sys.stdin.readline().strip()
 
joi_count = 0
ioi_count = 0
 
for i in range(len(s) - 2):
    segment = s[i : i + 3]
    if segment == "JOI":
        joi_count += 1
    elif segment == "IOI":
        ioi_count += 1
 
print(joi_count)
print(ioi_count)

복잡도

• 시간: O(N)
• 공간: O(N)