백준 5525번 IOIOI (IOIOI)

정보

문제 바로가기 [클릭]

난이도: Silver2

관련 개념: #문자열

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 P_N이라고 한다.

• P₁ IOI
• P₂ IOIOI
• P₃ IOIOIOI
• P_N IOIOI…OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P_N이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

---

출력

S에 P_N이 몇 군데 포함되어 있는지 출력한다.

---

제한

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

---

채점 및 기타 정보

• 예제는 채점하지 않는다.

---

예제 입출력 1

입력

1
13
OOIOIOIOIIOII

출력

4

해설

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

---

예제 입출력 2

입력

2
13
OOIOIOIOIIOII

출력

2

해설

• OOIOIOIOIIOII
• OOIOIOIOIIOII

---

코드(파이썬)

import sys


def getPI(base):
    pi = [0 for _ in range(len(base))]
    j = 0

    for i in range(1, len(pi)):
        if base[i] == base[j]:
            j += 1
            pi[i] = j
        else:
            while base[i] != base[j] and j > 0:
                j = pi[j-1]

    return pi

def kmp(base, target):
    pi = getPI(target)
    j = 0
    result = 0
    
    for i in range(len(base)):
        if base[i] == target[j]:
            if j == n * 2:
                result += 1
                j = pi[j]
            else:
                j += 1
        else:
            while base[i] != target[j] and j > 0:
                j = pi[j-1]
            
            if base[i] == target[j]:
                j += 1

    return result
        
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
base = sys.stdin.readline().rstrip('\n')
target = ("IO" * n) + "I"

print(kmp(base, target))

---

특이사항

• KMP 알고리즘 설명 및 그림을 보고 직접 구현했지만 그만큼 효율성 떨어지는 결과를 보임
  • 찾고 싶은 문자열의 접두사-접미사 리스트 생성
  • 원래 문자열에서 순서대로 글자 1개와 찾고 싶은 문자열을 비교
    • 찾고 싶은 문자열과 일치한다면 결과에 1을 더함
    • 찾고 싶은 문자열과 다르다면 접두사-접미사 리스트를 이용해 찾고 싶은 문자열의 가장 가까운 글자까지 이동
• 내 코드(57,796KB, 368ms)에 비해 우수한 코드(바로가기, 32,816KB, 84ms)와 비교

  • import sys
    
    def main():
        k = int(sys.stdin.readline())-1
        _ = int(sys.stdin.readline())
        strings = [len(i)-1 for i in sys.stdin.readline().strip().replace("IO", "X").replace("XI","XXO").replace("I","O").split("O") if i != ""]
        ans = 0
        for i in strings:
            ans += i-k if i > k else 0
        print(ans)
    
    if __name__ == "__main__":
        main()
    
    

  • 탐색 과정
    • 기존: KMP 알고리즘 사용
    • 개선: 입력 문자열 → ‘IO’를 ‘X’로 변환 → ‘XI’를 ‘XXO’로 변환 → ‘I’를 ‘O’로 변환 → ‘O’를 기준으로 나눠 리스트 생성 = i → i의 길이에 1을 뺸 값을 strings 리스트에 저장(IOI가 겹쳐진 갯수 = X의 개수(i의 길이)-1) → k보다 큰 i에 한해 i-k를 결과에 저장

---

참고문헌

• 멍멍멍, “KMP : 문자열 검색 알고리즘”, bowbowbow, https://bowbowbow.tistory.com/6
• injae Kim, “KMP 문자열 탐색 알고리즘이 동작하는 구체적인 원리”, Injae’s devlog, https://injae-kim.github.io/dev/2020/07/23/all-about-kmp-algorithm.html