[BOJ] 백준 5525 IOIOI (Swift)

문제

https://www.acmicpc.net/problem/5525

풀이

문자열 S에서 다음 조건을 만족하는 패턴 Pn이 몇 번 등장하는지 찾는 문제입니다.

• Pn의 정의:
  • P1: IOI
  • P2: IOIOI
  • P3: IOIOIOI
  • …
  • 즉, I로 시작해서 OI가 N번 반복되는 패턴
• 예를 들어, N = 2, S = IOIOIOI 라면 P2 패턴이 2번 등장할 수 있습니다 (겹쳐도 인정).

풀이 과정

• 패턴은 항상 "IOI" 형태를 기본 단위로 삼기 때문에, 문자열을 3글자씩 묶어가며 "IOI"를 계속 찾습니다.
• "IOI"가 연속될 경우 → count += 1
• 연속된 IOI가 N개가 되면 Pn 패턴 하나 완성 → result += 1
• 겹치는 패턴을 위해 count -= 1 처리

소스코드

후기

문자열 문제였는데, M이 최대 100만이므로, O(M)으로 풀어야하는 문제였다.
어떻게 하면 O(M)으로 풀 수 있을 지 생각해보면서 차근차근 풀었따..