파이썬 알고리즘 251번 | [백준 5525번] IOIOI - 규칙 발견하기

Yunny.Log ·2022년 8월 21일

Algorithm

목록 보기

256/318

251. IOIOI

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>


import sys

n = int(sys.stdin.readline() )
m = int(sys.stdin.readline() )
s = sys.stdin.readline() 

sum_tobe_n = 0
answer = 0
st = 0 # start idx 

while st <=m-2 :
    isIOI = s[st:st+3]

    if isIOI=='IOI' : 
        # IOI OIOI
        # ↑ 여기서 IOI 발견했다 치면 
        # 뒤에 OI(인덱스 2만큼)은 또 검사 안해도됨

        # IOI OIOI
        #     ↑ 
        # 따라서 인덱스 (st)에 2 더해줘서 그 뒤부터 검사
        
        sum_tobe_n+=1
        st+=2
        # sum_tobe_n 이 n개가 나오면 target 찾은 것
        if sum_tobe_n == n :
            answer+=1
            sum_tobe_n-=1 
            # answer 에 추가될 때마다 한 경우 추가된 것,
            # 기존에 IOI 발견해서 하나 더했던 것 써버렸으니 빼줘

    else : 

        st+=1
        sum_tobe_n = 0
    
print(answer)

<내 틀렸던 / 부분 성공했던 풀이, 문제점>

아래는 50점 풀이다.


import sys

answer = 0
n = int(sys.stdin.readline() )
target = 'IOI'
target += 'OI'*(n-1)

m = int(sys.stdin.readline() )
s = sys.stdin.readline() 

for st in range(m-len(target)+1) :
    now = s[st:st+len(target)]
    # print(now, target)
    if now==target :
        answer+=1

print(answer)

100점을 위해선 단일 for문을 이용해서 구현해야하는데 문자열이 규칙이 존재하기 때문에 단순 비교가 아니라 연산을 통해서 문자열을 찾아야한다.

IOI가 몇 번 연속되는지 갯수만 찾아서 체크하게 되면 N * 3 정도의 시간으로 문제를 풀 수 있게 된다.
IOI가 발견되면 index를 2개 이동시키고 아닌 경우에는 index를 1개 이동 시키면서 검사

import sys

answer = 0
n = int(sys.stdin.readline() )
target = 'IOI'
target += 'OI'*(n-1)

m = int(sys.stdin.readline() )
s = sys.stdin.readline() 

for st in range(m-len(target)+1) :
    isIOI = s[st:st+3]
    
    if isIOI=='IOI' : 
        chk = s[st:st+len(target)]
        if chk == target : 
            answer+=1
        st+=2
    
print(answer)