5525번 - IOIOI
시간제한 : 1초
메모리 제한 : 256MB
문제
N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 P𝚗이라고 한다.
- P₁ IOI
- P₂ IOIOI
- P₃ IOIOIOI
- P𝚗 IOIOI...OI (O가 N개)
I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P𝚗이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.
출력
S에 P𝚗이 몇 군데 포함되어 있는지 출력한다.
제한
S에 P𝚗이 몇 군데 포함되어 있는지 출력한다.
- 1 ≤ N ≤ 1,000,000
- 2N+1 ≤ M ≤ 1,000,000
- S는 I와 O로만 이루어져 있다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 50 | N ≤ 100, M ≤ 10 000. |
| 2 | 50 | 추가적인 제약 조건이 없다. |
예제 입력 1
1
13
OOIOIOIOIIOII예제 출력 1
4코드 1 - 50점
시간 : 52ms
메모리 : 31256KB
import sys
N = int(sys.stdin.readline().strip())
M = int(sys.stdin.readline().strip())
S = sys.stdin.readline().strip()
P = 'IO'*N + 'I'
cnt = 0
for i in range(M):
if S[i] == 'I':
if S[i:i+(N*2+1)] == P and i <= M:
cnt += 1
print(cnt)코드 2 - 100점
시간 : 388ms
메모리 : 33212KB
import sys
N = int(sys.stdin.readline().strip())
M = int(sys.stdin.readline().strip())
S = sys.stdin.readline().strip()
P = 'IOI'
cnt = i = answer = 0
# 입력받은 S의 길이만큼 반복
while i < (M - 1):
# 현재 반복되는 문자열이 'IOI'냐 ?
if S[i : i+3] == P:
# 그렇다면 다음에도 반복하는지 확인하기 위해 i+2
i += 2
# 'IOI' 반복 수 저장
cnt += 1
# 반복 수 cnt가 우리가 원하는 N과 동일하냐 ?
if cnt == N:
# 그렇다면 Pn을 찾은 것이므로 answer + 1
answer += 1
# 지금 Pn의 일부를 포함해서 또다른 Pn이 나올 수 있으므로
# cnt를 초기화하지 않고 -1만 함
cnt -= 1
# 현재 반복되는 문자열이 'IOI'가 아니냐 ?
else:
# 그럼 다음 인덱스로 이동
i += 1
# cnt 초기화
cnt = 0
print(answer)풀이
시간 : 40ms
메모리 : 31348KB
나는 이 문제를 간단한 인덱싱 문제라고 생각해서 코드 1과 같이 풀이했다가 50점을 맞았다.
따라서 주어지는 문자열에는 규칙이 존재하므로 인덱싱을 이용한 단순 비교가 아닌 연산을 해야한다.
핵심 코드는 아래 부분들이다.
# 현재 반복되는 문자열이 'IOI'냐 ?
if S[i : i+3] == P:
# 그렇다면 다음에도 반복하는지 확인하기 위해 i+2
i += 2
# 'IOI' 반복 수 저장
cnt += 1
# 반복 수 cnt가 우리가 원하는 N과 동일하냐 ?
if cnt == N:
# 그렇다면 Pn을 찾은 것이므로 answer + 1
answer += 1
# 지금 Pn의 일부를 포함해서 또다른 Pn이 나올 수 있으므로
# cnt를 초기화하지 않고 -1만 함
cnt -= 1-
먼저 현재 부분에서 문자열들이
IOI라면N개만큼 반복하나 확인하기 위해i에2를 더해IO를 지나I에서부터 다시 비교하고,cnt에IOI의 반복 수를 저장한다. -
만약 현재
IOI의 반복 수cnt가 주어진N과 동일하다면Pn을 찾은 것이므로Pn개수를answer에1을 더하고, 현재Pn의 일부를 포함해또다른 Pn이 나올 수 있으므로cnt를0으로 초기화하지 않고-1만 한다.
끄적끄적