[Python] BOJ/백준 5525번 IOIOI

[문제]
www.acmicpc.net/problem/5525

5525번: IOIOI

 

 

[풀이]

처음에는 부분성공 코드로 제출한 후 아무리 생각해도 답을 모르겠어서 다른 사람 풀이를 찾아봤다.

성공한 코드는 문자열을 만들어서 비교하지 않고 s 내부에서 패턴을 찾아 비교하는 풀이이다.

 

풀이 중 이해가 안돼서 고민하던 부분을 주석에 숫자로 남겨놓았는데

1. cnt -= 1

   : 일치할 경우 첫 번째 'IOI' 패턴 이후부터 검사해야 하기 때문에 cnt에서 1을 뺀다.

2. i += 1

   : 'IOI' 패턴이 나왔을 때 다음 문자는 계속 'OI'가 반복되어야 함.

     조건문은 s[i-1]부터 검사하기 때문에 i를 1 더 증가시켜야 함

 

[코드]

- 부분성공(50점)

import sys


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()

    pn = ''
    for i in range(n*2+1):
        if i % 2 == 0:
            pn += 'I'
        else:
            pn += 'O'

    cnt = 0
    for i in range(m - len(pn)):
        if s[i:i+len(pn)] == pn:
            cnt += 1
    print(cnt)

 

- 제출 코드

import sys


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()

    ans = 0
    cnt = 0
    i = 1
    while i < m - 1:
        if s[i-1] == 'I' and s[i] == 'O' and s[i+1] == 'I':
            cnt += 1
            if cnt == n:
                cnt -= 1    # 1
                ans += 1
            i += 1  # 2
        else:
            cnt = 0
        i += 1

    print(ans)