[Silver I] IOIOI - 5525

문제 링크

성능 요약

메모리: 31120 KB, 시간: 32 ms

분류

문자열

제출 일자

2024년 11월 13일 00:22:05

문제 설명

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이 몇 군데 포함되어 있는지 출력한다.

풀이

n = int(input())
m = int(input())
p = ""

for i in range(2 * n + 1):
    if i % 2:
        p += "O"
    else:
        p += "I"

s = input()
cnt = 0

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

print(cnt)

처음에 이렇게 코드를 작성하면 되겠다 싶어 제출하니 50점이 나온다. 시간복잡도 문제로 50점이 안 나온 것 같다.

생각을 해보다가 어떻게 풀어야 하는지 도저히 생각이 나지 않았다. 인터넷에 찾아보니 문자열 인덱싱이 아닌 연상을 이용하여 푼다고 한다.

n = int(input())
m = int(input())
s = input()
cnt, i, result = 0, 0, 0

while i < m - 2:
    if s[i:i+3] == "IOI":
        i += 2
        cnt += 1
        if cnt == n:
            result += 1
            cnt -= 1
    else:
        i += 1
        cnt = 0

print(result)

풀이는 문자열 3개를 잘아서 `IOI`가 나온다면 `cnt`를 하나 증가시키면서 `i`를 2 증가시킴으로 `IOI`의 뒷쪽 I로 인덱스가 향하도록 하였다. cnt와 n이 같아지면 P가 되기 때문에 result를 1 증가시키고 cnt를 1 감소시켜 또 찾을 수 있도록 해준다.

`IOI`가 아니라면 바로 뒤의 문자를 확인할 수 있도록 한다. 이를 문자를 3칸 기준으로 보기 때문에 i가 m - 2보다 작을 때까지만 갈 수 있도록 해줬다.