[백준] IOIOI

[백준] IOIOI

---

풀이

문제의 조건은 다음과 같다.

1. N+1 개의 “I” 와 N 개의 “O” 로 이루어진 문자열이 있을 때, 이 문자열을 $ P_{N} $ 이라고 한다.

2. I와 O로 이루어진 문자열 S와 정수 N이 주어질 때, S안에 들어있는 $ P_{N} $ 패턴의 개수를 구하는 방법을 찾는다.

# 50점
n = int(input())
M = int(input())
S = input()

pn = "IO"*n + "I"
cnt = 0

while S.find(pn) > -1:
  S = S[S.find(pn)+2:]
  cnt += 1

print(cnt)

# 정답
N = int(input())
M = int(input())
S = input()

count = 0
cnt = 0
i = 1
while i < M - 1:
    if S[i-1] == "I" and S[i] == "O" and S[i+1] == "I":
        count += 1
        if count == N:
            count -= 1
            cnt += 1
        i += 1
    else:
        count = 0
    i += 1

print(cnt)

---

실수 및 배운 점

• 첫번째 만들었던 방법은 슬라이싱을 이용해서 ‘앞’에서 부터 문자열을 끊어줬다.
  PN = “IOI” 라고 할 때, S =IOIOIOIIIOO 라고 한다면,
  앞자리인 “IO” 반복되기 때문에,
  find를 이용해서 PN과 같은 문자열이 있는 index를 찾고 cnt를 올릴 수 있도록 했다.
  1) IOIOIOIIIOO, cnt = 1
  2) IO(자름) IOIOIIIOO, cnt = 2
  3) IOIO(자름) IOIIIOO, cnt = 3
  이런식으로 자르면서 갯수를 셀 수 있도록 했다.
  하지만, 시간 초과!

• 두번째 방법은 구글링하면서 찾을 수 있었다.
  위와 같은 문제라 가정했을 때,
  index를 기준으로 좌우를 확인한 다음에 PN이 아닌 “IOI”을 찾는다.
  패턴을 찾는다면, index + 2를 하면서 PN과 같은 패턴이 될 때 까지 찾는다.
  PN을 찾는다면 count를 N-1 개로 만들어주고 index + 2를 해서 그 기준으로 좌우에 IOI가 있는 지 확인하면서 PN을 찾는다.
  즉, 패턴이 IOI가 반복된다는 것을 이용한다.

  1) IOIOIOIIIOO, cnt = 1
  2) IOIOIOIIIOO, cnt = 2
  3) IOIOIOIIIOO, cnt = 3

• 두 방법의 차이라면, PN을 찾는 것과 “IOI”라는 패턴을 찾는 것의 차이인 것 같다.
  내 예상으로는 PN이 너무 길면 find를 통해 패턴을 찾을 때 시간초과가 뜨는 것 같다.
  슬라이싱을 IOI만을 이용해서 풀어도 될 것 같다.

• KMP 알고리즘 활용 방법 찾아보기