BOJ(백준) 5525[IOIOI]

안녕하세요, 이번 글에서는 백준 5525번 문제인 “IOIOI” 문제를 함께 해결해 보겠습니다. 이 문제는 주어진 문자열에서 특정 패턴이 몇 번 나타나는지 계산하는 문제입니다. 함께 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

문제 URL: https://www.acmicpc.net/problem/5525

 

1. 문제 설명

1) 문제 개요

• 주어진 문자열 S에서 특정 패턴 ‘IOI’가 반복되는 횟수를 찾는 문제입니다.

• 패턴 ‘IOI’가 N번 반복되는 문자열을 찾아야 합니다. 예를 들어, N=1일 때 패턴은 ‘IOI’, N=2일 때 패턴은 ‘IOIOI’입니다.

• 주어진 문자열 S에서 이러한 패턴이 몇 번 등장하는지 계산하는 문제입니다.

 

2) 입력

• 첫 번째 줄에 패턴의 반복 횟수 N이 주어집니다. (1 ≤ N ≤ 1,000,000)

• 두 번째 줄에 문자열 S의 길이 M이 주어집니다. (2N + 1 ≤ M ≤ 1,000,000)

• 세 번째 줄에 문자열 S가 주어집니다.

 

3) 출력

• 문자열 S에서 주어진 패턴이 몇 번 등장하는지 출력합니다.

 

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 패턴의 반복 횟수 N을 입력받습니다.

• 두 번째 줄에서 문자열 S의 길이 M을 입력받습니다.

• 세 번째 줄에서 문자열 S를 입력받습니다.

 

2) 패턴 찾기

• 문자열 S를 순회하면서 ‘IOI’ 패턴을 찾습니다.

• 패턴이 겹칠 수 있기 때문에 인덱스를 2씩 전진하며 검사합니다.

• 패턴을 찾으면 패턴의 반복 횟수를 증가시키고, 원하는 반복 횟수에 도달하면 정답 카운트를 증가시킵니다.

 

3) 코드 설명

• 첫 번째 줄에서 패턴의 반복 횟수 N을 입력받습니다.

• 두 번째 줄에서 문자열 S의 길이 M을 입력받습니다.

• 세 번째 줄에서 문자열 S를 입력받습니다.

• 문자열 S를 순회하며 패턴을 찾고, 패턴이 끊길 때마다 카운트를 초기화합니다.

• 최종적으로 찾은 패턴의 개수를 출력합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# N: IOI 패턴의 반복 횟수
N = int(input())
# M: 문자열 S의 길이
M = int(input())
# S: 주어진 문자열
S = input()

i = 0          # 현재 문자열 S에서의 인덱스
pCnt = 0       # IOI 패턴의 현재 반복 횟수
ans = 0        # 찾은 패턴의 총 개수

# 문자열의 끝까지 검사
while i < (M-1):
    # 'IOI' 패턴을 찾았을 때
    if S[i] == 'I' and S[i+1] == 'O' and S[i+2] == 'I':
        pCnt += 1        # IOI 패턴의 반복 횟수를 증가
        i += 2           # 패턴이 겹치므로 2칸 전진
        # 패턴이 N번 반복되면 정답 카운트 증가
        if pCnt == N:
            ans += 1
            pCnt -= 1    # 중복된 패턴을 고려하기 위해서 pCnt를 1 감소
    else:
        pCnt = 0         # 패턴이 끊기면 pCnt를 초기화
        i += 1           # 1칸 전진

# 최종적으로 찾은 패턴의 개수 출력
print(ans)

 

4. 코드 설명

1) 입력 받기

• 첫 번째 줄에서 패턴의 반복 횟수 N을 입력받습니다.

• 두 번째 줄에서 문자열 S의 길이 M을 입력받습니다.

• 세 번째 줄에서 문자열 S를 입력받습니다.

 

2) 변수 초기화

• i: 현재 문자열 S에서의 인덱스를 나타냅니다. 초기값은 0입니다.

• pCnt: 현재까지 찾은 ‘IOI’ 패턴의 반복 횟수를 나타냅니다. 초기값은 0입니다.

• ans: 찾은 패턴의 총 개수를 나타냅니다. 초기값은 0입니다.

 

3) 문자열 순회 및 패턴 찾기

• 문자열 S를 순회하면서 ‘IOI’ 패턴을 찾습니다.

 

• 예를 들어, 문자열 S가 IOIOIOI이고 N이 2인 경우로 설명하겠습니다.

1] 초기 상태

  • i = 0, pCnt = 0, ans = 0

2] 첫 번째 패턴 찾기

  • S[0] == 'I', S[1] == 'O', S[2] == 'I'이므로 ‘IOI’ 패턴을 찾았습니다.

  • pCnt += 1 -> pCnt = 1

  • i += 2 -> i = 2 (패턴이 겹칠 수 있으므로 2칸 전진)

3] 두 번째 패턴 찾기

  • S[2] == 'I', S[3] == 'O', S[4] == 'I'이므로 다시 ‘IOI’ 패턴을 찾았습니다.

  • pCnt += 1 -> pCnt = 2 (여기서 pCnt는 N과 같아집니다)

  • i += 2 -> i = 4

  • pCnt == N이므로 ans += 1 -> ans = 1

  • 중복된 패턴을 고려하기 위해 pCnt -= 1 -> pCnt = 1

4] 세 번째 패턴 찾기

  • S[4] == 'I', S[5] == 'O', S[6] == 'I'이므로 다시 ‘IOI’ 패턴을 찾았습니다.

  • pCnt += 1 -> pCnt = 2 (여기서 다시 pCnt는 N과 같아집니다)

  • i += 2 -> i = 6

  • pCnt == N이므로 ans += 1 -> ans = 2

  • 중복된 패턴을 고려하기 위해 pCnt -= 1 -> pCnt = 1

5] 더 이상 검사할 패턴이 없으므로 종료합니다.

 

4) 최종 결과 출력

• 최종적으로 찾은 패턴의 개수 ans를 출력합니다.

 

시간복잡도

루프가 문자열 S를 한 번 순회하면서 모든 패턴을 검사하므로, 전체 시간복잡도는 O(M)입니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_08_04_5525.py at main · pcy4196/coTest