반응형
5525번: IOIOI
N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇
www.acmicpc.net
문제
N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.
- P1 IOI
- P2 IOIOI
- P3 IOIOIOI
- PN IOIOI...OI (O가 N개)
I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.
출력
S에 PN이 몇 군데 포함되어 있는지 출력한다.
제한
- 1 ≤ N ≤ 1,000,000
- 2N+1 ≤ M ≤ 1,000,000
- S는 I와 O로만 이루어져 있다.
서브태스크
번호 | 배점 | 제한 |
1 | 50 | N ≤ 100, M ≤ 10 000. |
2 | 50 | 추가적인 제약 조건이 없다. |
예제 입력 11
13 OOIOIOIOIIOII |
예제 출력 14
|
- OOIOIOIOIIOII
- OOIOIOIOIIOII
- OOIOIOIOIIOII
- OOIOIOIOIIOII
예제 입력 22
13 OOIOIOIOIIOII |
예제 출력 22
|
- OOIOIOIOIIOII
- OOIOIOIOIIOII
풀이
특정 문자열에 패턴이 몇 번 나오는지 세어 출력하는 문제이다.
패턴의 길이가 p라고 할 때, 브루트 포스로 인덱스 0부터 M-p 까지 순환하며 패턴을 일일이 확인한다면 시간 초과가 발생할 것이다.
이 문제를 해결하기 위해 다양한 알고리즘이 사용될 수도 있겠지만, 필자는 문자열 S를 딱 한 번만 돌며 반복되는 OI를 구하기로 했다.
예제 2을 예로 들겠다.
- OOIOIOIOIIOII
인덱스 2~6 위치에서 패턴이 발견되었다.
그렇다면 그 다음 패턴을 찾는 방법은 다시 인덱스 3부터 패턴을 대조해보는 것이 아닌, 그 뒤의 OI 두개만 확인하면 되는 것이다.
만약, OI가 순서대로 오지 않고 패턴에 어긋난다면 그 위치부터 다시 패턴 대조를 시작한다.
import sys
input = sys.stdin.readline
sys.stdin = open("pyt.txt","r")
def main():
n = int(input())
m = int(input())
s = input().rstrip()
ans,cor = 0,1
start = False
OI,OIb = ["O","I"],False
for i in range(m):
# 모든 패턴은 I부터 시작하므로, 대조중이 아닐 때 마주친 글자가 I이라면 대조를 시작한다.
if start == False and s[i] == "I":
start = True
OIb = False
continue
if start:
if s[i] == OI[OIb]:
if OIb == True:
cor += 1
OIb = not OIb
continue
else:
if s[i] == "O":
start = False
# 대조 종료이므로 결과 더하기
ans += max(0,cor-n)
OIb = False
cor = 1
ans += max(0,cor-n)
print(ans)
if __name__ == "__main__":
main()
반응형
'알고리즘 연습 > 구현, 문자열' 카테고리의 다른 글
[🥉2 / 백준 10102 / 파이썬] 개표 (0) | 2022.03.01 |
---|---|
[🥉2 / 백준 5355 / 파이썬] 화성 수학 (0) | 2022.02.24 |
[🥉2 / 백준 2789 / 파이썬] 유학 금지 (0) | 2022.02.08 |
[🥉2 / 백준 2711 / 파이썬] 오타맨 고창영 (0) | 2022.02.05 |
[🥉2 / 백준 2592 / 파이썬] 대표값 (0) | 2022.01.31 |