백준 5525번: IOIOI (S1) - Python 풀이

오늘의 문제

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

 

내 풀이

난 솔직히 어려웠다. 맞힌 코드만 보면 너무 쉬운데, 이 방법을 생각해내는 것이 어려웠다.

처음에는 N값에 맞는 Pn을 만들고, S를 순회하면서 Pn이랑 S를 '한 글자씩' 비교하여 어쩌구... 하는 방식으로 접근했다가 

ㅋㅋ

이렇게 계~속 안 풀려서 접근이 틀렸다고 생각하고 서치를 해봤다.

 

N = int(input())
M = int(input())
S = input()

P1 = "IOI" # 기본단위 P1 생성
continuous_cnt = 0 # P1이 반복되는 횟수를 저장하는 변수
i = 0 # S를 슬라이싱 할 시작 인덱스
answer = 0

# i+3이 M이 될 때까지 (즉, 최대 M-1까지 슬라이싱 가능)
while i < M - 2:
	# S의 i부터 i+2까지가 IOI라면
    if S[i : i+3] == P1:
    	# P1이 반복되는 횟수 1 증가
        continuous_cnt += 1
        # 인덱스 2칸 이동
        i += 2
        # 반복 횟수가 N이면 (즉, S에서 Pn을 찾았으면)
        if continuous_cnt == N:
            answer += 1 # 정답 +1
            continuous_cnt -= 1 # 찾은 Pn과 IOI가 겹치는 부분이 있을 수 있기 때문에 반복 횟수를 1개만 줄여놓는다
    # IOI(= P1)가 아니라면
    else:
    	# P1부터 다시 찾아야 하니까 반복 횟수를 초기화
        continuous_cnt = 0
        # 인덱스 1칸만 이동
        i += 1

print(answer)

풀이 참고한 블로그 : https://velog.io/@hamsangjin/백준-5525번-IOIOI-파이썬

 

Damn... 기본 단위인 P1만 만들어두고, S를 slicing 해서 P1과 비교하는 방식을 발견했다. 슬라이싱 생각도 못 했는데.

P1을 통째로 가져다가 쓰기 때문에 IOIOI 처럼 I 사용이 겹치는 부분도 고려가 가능했고, S와 Pn을 각각 한 글자씩 확인해야 할 때보다 훨씬 간단하게 풀이가 가능했다.

 

핵심은 1) S를 슬라이싱 해서 P1과 통째로 비교 2) S 안에서 Pn을 찾은 후, 이후 탐색에서 이전에 찾은 Pn과 겹치는 부분을 고려하기 위해 continuous_cnt를 1개만 빼는 부분 인 것 같다.