5525

날짜 : 2023. 02. 06

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())  # OI 개수
m = int(sys.stdin.readline())  # 문자열 길이
s = sys.stdin.readline().rstrip()  # 문자열
res = 0
now, cnt = 0, 0 # now : 현재 기준점 / cnt : 연속성 체크용

while now < (m - 1):
    if s[now:now + 3] == "IOI":  # IOI인 경우
        cnt += 1 # 연속 체크
        now += 2  # 2칸 이동
        if n == cnt:
            res += 1
            cnt -= 1 # 맨 앞 IOI 삭제(찾았으니까 필요 x)
    else:
        cnt = 0
        now += 1

print(res)

 

 

풀이

- 문자열 슬라이싱으로 하나씩 비교하다보면 시간복잡도가 O(n * m)으로 나타나기 때문에 결국 TLE가 발생한다(50점)

- 그래서 시간복잡도를 줄이기 위해 문자열 슬라이싱을 사용하기보다는 "IOI"를 비교하면서 연속된 경우를 체크하면서 연속된 횟수가 기준이 되는 IOI의 개수와 동일한 경우에 결과값을 중가시키는 방향으로 코드를 전개한다.

- 또한 기준점이 "O"인 경우에는 기준 문자열과는 다를 것이기 때문에 비교를 하지 않고 넘어간다.

- 또한 연속되는게 끊길 경우에도 연속되는 개수(cnt)를 0으로 초기화함으로써 처음부터 셀 수 있도록 설정한다.

 

 

알게된 점

- 50점은 쉽게 얻었는데 이중 반복문을 계속 생각하다보니 정답이 곧바로 연상되지 않았다.

- 식을 세워서 풀어보려 하기도 했고, for문 안에서 "I"를 발견했을 때만 for문을 넣어 비교하는 방식으로 풀어보려 했지만 계속 TLE가 발생했다.

- 결국 한시간정도 고민하고 찾아보니 연속되는 개수를 가산 / 0으로 초기화하면서 문제를 해결하는 것이 골자였다.

(해당 풀이를 사용했을 때의 시간복잡도는 O(3 * m))

 

 

참고 사이트

-