[Python | 백준] 5525번: IOIOI

문제 요약

N+1개의 I와 N개의 O로 이루어진 문자열을 PN이라고 한다. 예를 들어, P1은 "IOI", P2는 "IOIOI", P3는 "IOIOIOI"이다. 주어진 문자열 S 안에 PN이 몇 번 포함되어 있는지 찾는 프로그램을 작성하는 문제이다.

 

풀이 설명

문제의 본질은 문자열 S 안에 PN 패턴이 몇 번 포함되어 있는지를 찾는 것이다.

이를 위해 문자열을 순회하면서 IOI 패턴을 찾고, N개의 IOI 패턴이 연속적으로 등장할 때마다 카운트를 증가시키는 방식으로 해결할 수 있다.

 

N = int(input())
M = int(input())
S = input()

def count_pn(N, S):
    pattern_count = 0
    i = 0
    count = 0

    while i < len(S) - 1:
        if S[i:i+3] == "IOI":
            count += 1
            i += 2 # 다음 I로 이동
            if count == N:
                pattern_count += 1
                count -= 1 # 패턴 중첩될 수도 있으므로
        else:
            count = 0
            i += 1

    return pattern_count

print(count_pn(N, S))

 

코드 설명

1. 변수 초기화:
   • pattern_count: PN 패턴의 총 개수를 저장.
   • i: 현재 문자열 S를 순회하는 인덱스.
   • count: 연속된 "IOI" 패턴의 수를 세기 위한 변수.
2. 문자열 순회:
   • 문자열 S를 순회하면서 "IOI" 패턴을 찾는다.
   • 만약 "IOI" 패턴을 찾으면, count를 1 증가시키고 i를 2 증가시킨다. 이는 다음 I로 이동하기 위함이다.
   • count가 N에 도달하면 pattern_count를 1 증가시키고, 중첩된 패턴을 고려해 count를 1 감소시킨다.
   • 만약 "IOI" 패턴이 아닌 경우, count를 0으로 초기화하고 i를 1 증가시킨다.
3. 결과 반환:
   • 최종적으로 pattern_count를 반환한다. 이는 주어진 문자열 S 안에 PN 패턴이 몇 번 포함되어 있는지를 나타낸다.

이 방식은 문자열 S를 한 번 순회하며 필요한 패턴을 찾아내므로 시간 복잡도는 O(M)이다. N과 M이 모두 최대 1,000,000까지 가능하므로, 이 방법은 효율적이다.