[Python] 5525번 IOIOI

문제

풀이과정

• 입력

  N: O의 개수

  M: S의 길이

  S: I,O로만 이루어진 문자열
  

• 출력

  S에 Pn이 몇군데 포함되어있는지
  

• 접근법

  연속으로 문자열 S가 나온다면 +1을 카운트 해준다.

  P1: IOI

  P2: IOIOI

  P3: IOIOIOI

  규칙을 생각해보면 N은 IOI가 나오는 개수이다.

  while i < M-1:  # 1 ~ M-1
      if S[i-1] == "I" and S[i] == "O" and S[i+1] == "I":
          cnt += 1
          if cnt == N:
              ans += 1
              print(i, cnt)
      else:
          cnt = 0
      i += 1

  N 은 IOI의 개수니까 cnt가 N과 같으면 1번 나온 것과 같다.

  첫번째 예제는 잘 작동하지만 IOI가 2번 있는 것 부터는 규칙이 더 필요하다.

  IOI가 나온 후에는 OI가 나오기 때문에 건너뛰어준다. i + 2

  if S[i-1] == "I" and S[i] == "O" and S[i+1] == "I":
          cnt += 1
          i += 2 # 이미 처리된 문자 건너뛰기 
      # N 은 IOI의 개수니까 cnt가 N과 같으면 1번 나온 것과 같다.
          if cnt == N:
              ans += 1
              print(i, cnt)
      else:
          i += 1
          cnt = 0

  • OOIOIOIOIIOII

  예제입력 2 인데 i =3 일때 처음 IOI를 만나고 OIO는 건너뛰고 다음 IOI를 세기 위해서 i += 2 를 수행하면 i = 5일 때 다음 IOI를 만날 수 있다.

  또한, cnt -= 1을 하는 이유도 살펴볼 수 있었다.

  i = 5일 때 만난 IOI 부터 cnt = 1이기 때문에 다음 것 부터 생각하기 위해 cnt -= 1을 수행하는 것이다.
  

정답

    import sys
    input = sys.stdin.readline
    
    N = int(input().rstrip())
    M = int(input().rstrip())
    S = input().rstrip()
    
    cnt = 0
    i = 1
    ans = 0
    
    while i < M-1:  # 1 ~ M-1
        if S[i-1] == "I" and S[i] == "O" and S[i+1] == "I":
            cnt += 1
            i += 2  # 이미 처리된 문자 건너뛰기
        # N 은 IOI의 개수니까 cnt가 N과 같으면 1번 나온 것과 같다.
            if cnt == N:
                ans += 1
                cnt -= 1
    
        else:
            i += 1
            cnt = 0
    
    print(ans)

이번 문제도 그렇고, 재귀/dp문제 등을 풀 때에도 제일 간단한 예제만 생각했을 때에는 코드가 완성되지 않았고, 3가지 예제정도 생각해보아야 규칙을 제대로 찾을 수 있는 것 같다.