[Backjoon 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이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

 

풀이

---

1. Subtask1 -> 50점

 

미리 P1, P2..에 대한 정답을 sol만들고 슬라이싱 방법을 통해 루프를 돌며 sol과 같은 부분이 있으면 count하는 방식으로 구현했다.

n = int(input())
m = int(input())
data = input()
sol = 'I' + 'OI' * n

result = 0
for i in range(0, len(data) - len(sol) + 1):
    if data[i] == 'I' and data[i:i+len(sol)] == sol:
        result += 1

print(result)

 

2. Subtask2 -> 100점 

Subtask1의 경우 input의 길이에 제한이 있어서 모든 루프를 돌아도 시간초과가 나지않는다. 하지만 subtask2에서는 제한사항이 없기 때문에 이를 고려해서 코드를 구현해야한다.

문자열의 모든 인덱스를 확인하는 것이 아닌 'IOI'의 등장 횟수만을 고려하면 된다.

n = int(input())
m = int(input())
data = input()

i = 0
result = 0
data_cnt = 0
while i < m - 1: # 인덱스 범위를 넘으면 안되므로
    if data[i:i+3] == 'IOI': # IOIOI -> IOI가 2개
        i += 2 # 2칸씩 점프
        data_cnt += 1 # P에 따라서 연속된 IOI....OI가 결정되므로
        if data_cnt == n:
            result += 1
            data_cnt -= 1 # 위에서 나온 IOI..문자열의 마지막이 또다른 IOI와 이어질 수 있으므로
    else:
        i += 1
        data_cnt = 0
print(result)

특정 문자열이 얼마나 나오는지에 대한 문제는 subtask2와 같이 정답 문자열의 규칙을 찾고 해당 문자열의 길이만큼 슬라이싱하면서 시간 복잡도를 줄일 수 있다! 여기서 주의할 점은 data_cnt를 0으로 초기화하지 말고 1을 빼주는 것!