[구현/문자열] 백준 5525 IOIOI - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

5525번: IOIOI

 

 

 

2. 문제 풀이

 IOIOI가 주어진 문자열에 몇 번 포함되는지 구하는 문제입니다.

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 파이썬은 문자열 연산에 특화되어있다고 말해도 모자람이 없습니다. 그만큼 쉽습니다.

 IOI형태가 이어질 때마다 길이를 체크하고, Pn이상 길어지면 포함 횟수를 1씩 늘립니다

 

 

 

3. 코드

import sys
input = sys.stdin.readline

N = int(input()) #Pn
Pn = 'I'+"OI"*N

M = int(input()) #S의 길이
S = input().rstrip()

res = 0
i = 0
while i < M-len(Pn):
    #Pn이 있으면 1 카운트하고, 2칸 앞으로 이동
    if S[i:i+len(Pn)] == Pn:
        res += 1
        i += 1
    i += 1
print(res)

 한 칸씩 이동하면서, Pn이 포함되어있는지 확인했습니다. 위 코드는 Pn이 길어질수록 중복되는 비교연산이 많아집니다. 시간초과가 나진 않았지만, 50점으로 부분 정답처리되었습니다.

 

import sys
input = sys.stdin.readline

N = int(input()) #Pn
M = int(input()) #S의 길이
S = input().rstrip()

res = 0 #Pn이 나온 횟수
cnt = 0 #IOI카운트
for s in S:
    #IOI카운트에서 O는 짝수번째여야 함
    if s == 'O' and cnt%2 == 1:
        cnt += 1

    #IOI카운트에서 I는 홀수번째여야 함
    elif s == 'I' and cnt%2 == 0:
        cnt += 1

    #그 외의 I라면 맨 처음 I시작
    elif s == 'I':
        cnt = 1

    #그 외라면 카운트 아님
    else:
        cnt = 0

    #Pn만큼 IOI카운트세면 결과에 +1
    if cnt >= 1+2*N and cnt%2 == 1:
        res += 1
print(res)

 두 번째 코드는 문자열 S를 처음부터 끝까지 훑으면서 IOI형태가 이어지는지 체크했습니다. 중복되는 비교 연산이 없기 때문에 100점 통과했습니다.

 맨 처음 I가 나오면 카운트 1로 시작하며, 그 다음은 O가 나와야 합니다. IOIOIOI...에서 O는 짝수번째 위치이므로 그 전까지의 cnt는 홀수여야 합니다. 반대로 I는 홀수번째 위치이므로 그 전까지의 cnt는 짝수입니다.

 만약 위의 경우가 아니라면, IOIOI형태가 깨진 것이므로 cnt = 0으로 초기화합니다.