5525 - IOIOI

https://www.acmicpc.net/problem/5525

5525번: IOIOI

 

 

- 구현

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
s = input()[:-1]

p = 'I'
for _ in range(n):
    p += 'OI'

try:
    idx = s.index('IOI')
except:
    print(0)
    exit()

cnt = 0
for i in range(idx, m - 2*n):
    if s[i:i+(2*n+1)] == p:
        cnt += 1

print(cnt)

(하나씩 찾기 - 50점)

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
s = input()[:-1]

sn = ''
for i in s:
    sn += ('0' if i == 'O' else '1')

p = '1' + '01' * n
m = len(sn.lstrip('0'))
s = eval(sn.lstrip('0'))

cnt = 0
k = 10 ** (2*n + 1)
for _ in range(m - 2*n):
    if str(s % k) == p:
        cnt += 1
    s //= 10

print(cnt)

(숫자로 치환해서 10씩 나눠가며 구하기 - 50점)

 

import sys
input = sys.stdin.readline

def check(idx):
    if s[idx:idx+3] == 'IOI':
        return True
    else:
        return False

n = int(input())
m = int(input())
s = input().rstrip()

i, k, a = 0, 0, 0
while i <= m-2:
    if check(i):
        k += 1
        i += 2
    else:
        if k+1 > n:
            a += (k+1-n)
        k = 0
        i += 1

print(a)

(메모장에 적은 아이디어 - 100점)

 

별 똥꼬쇼를 다해도 100점이 안나와서 좀 포기했던 문제인데 다시 건드려봤다

뭐 느낀 점은 별게 없음.. 걍 오랜만에 풀어본 구현 문제?

 

+ arr[i:j]로 슬라이싱하면 j-i 만큼의 연산을 수행하기 때문에 첫 번째 코드는 시간 초과가 난다~

 

 

----------수정----------

메모장에 적은 아이디어로 했을 때 재채점 결과로 시간 초과가 떠서 약간 다르게 수정해봤더니 100점이 떴다.. 푼지 좀 오래돼서 아이디어 떠올리는게 힘들었는데 그래도 풀어서 기쁘당..

n = int(input())
m = int(input())
s = list(input())

i, cnt = 0, 0
record = list()

while(i < m-2):
    if s[i] + s[i+1] + s[i+2] == 'IOI':
        cnt += 1
        i += 2
    else:
        record.append(cnt)
        cnt = 0
        i += 1
record.append(cnt)

answer = 0
for var in record:
    if var < n: 
        continue

    answer += ((var + 1) - n)

print(answer)

 

뭐가 다르냐면?.. 흠.. record 리스트를 선언해서 거기에 IOI 개수를 담고 나중에 계산해준 것과, 문자열 s를 리스트로 받아서 슬라이싱 대신 문자열 합으로 비교해준 것? 솔직히 크게 차이 없고 오히려 메모장 아이디어가 더 적어보이는 거 같은데 잘 모르겟당..