[백준BOJ] 5525번 IOIOI.py

 

백준 저지에서 IOIOI를 파이썬을 통해 풀어 보았다.

 

https://www.acmicpc.net/problem/5525

5525번: IOIOI

5525번 IOIOI.py

tomy9729/Algorithm

 

 

5525번 IOIOI

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.
P1 IOI
P2 IOIOI
P3 IOIOIOI
PN IOIOI...OI (O가 N개)
I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

설명

긴 문자열에서 부분 문자열의 개수를 찾는 문제이다. index를 하나씩 추가하며 문자열을 비교하는 방법으로도 문제를 푼다면 시간 복잡도 O(nm)이 걸리며 시간 초과에 걸리게 된다. 시간 복잡도를 줄이는 방법을 생각해야 한다.

 

처음에는 라빈 카프 알고리즘을 통해 문제를 해결하려고 했다. 라빈 카프 알고리즘이란 해쉬 함수를 통해 문자열을 비교하는 방법이다. index를 이동하면서 양 끝 문자만 수정하여 부분 문자열과 비교하기 때문에 O(m)의 시간이 걸린다. 단 해쉬의 범위가 실제 문자열의 개수를 포옹하지 못하는 경우 해시 충돌이 발생하여 틀릴 가능성이 있다. 다른 방법이 필요했다.

 

부분 문자열은 "IOI" 패턴이 몇 번 나오는지가 중요하다. 긴 문자열의 index를 1씩 증가시키며 탐색하다가 "IOI" 패턴이 나오면 index를 2만큼 증가시켜 "IOI"패턴이 몇 번 반복되는지 확인한다. 만약 n번 반복된다면 부분 문자열을 탐색한 것이므로 체크한다. 이 방법을 통해 O(m)의 시간 복잡도로 문제를 해결할 수 있다.

 

"IOI"패턴이 겹치는 경우도 있으므로 "IOI"패턴이 n번 반복되었다면 패턴이 이어질 경우를 생각해 pattern 개수를 1 감소시킨다. 

코드

#5525번 IOIOI 
if __name__ == "__main__":
  n = int(input())
  m = int(input())
  s = input()

  answer = 0
  pattern = 0
  i = 0
  while i < m-2 : 
    if s[i] == "I" and s[i+1] == "O" and s[i+2] == "I" : 
      pattern += 1
      if pattern == n : 
        answer += 1
        pattern -= 1
      i += 2
    else : 
      pattern = 0
      i += 1
  print(answer)