Algorithm/백준(BOJ)

[Python] 5525 - IOI

Gr00t 2021. 3. 10. 18:32

문제

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

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 N이 주어진다.
  • 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.
  • (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)

출력

  • S에 PN이 몇 군데 포함되어 있는지 출력한다.

풀이

문자열의 반복 횟수를 찾는 문제다.

자세히는 IO가 반복되는 문자 덩어리?가 주어진 문자열에서 몇번이나 나오는지 확인하는 것이다.

1~2트

처음에는 문자열의 인덱스를 기반으로 하나씩 옮겨가며 find함수를 통해 찾은 갯수를 세려고 했다.

아래와 같이 함수를 작성하니 바로 시간초과가 떴다.

그냥 돌아가며 확인하는 것만 해도 최대 100만번인데 내부적으로 문자열하나하나 비교하는 연산까지 하면 당연한 결과일 것이다.

def ioioi(n, m, s):
    pn = 'I' + 'OI' * n
    cnt = set()
    i = 0
    while i < m:
        f = s.find(pn, i)
        if f == -1:
            break
        cnt.add(f)
        i = f+1
    return len(cnt)

3트

아무리 생각해도 더 빠르게 할 수 있는 방법이 생각나지 않아 다른 분들의 포스팅을 보며 방법을 찾아봤다.

맞은 분들은 하나 같이 문자열 전체를 비교하는 것이 아니라 IOI라는 문자단위로 비교한다는 것을 알 수 있었다. 인덱스를 2씩 증가시키며 IOI의 갯수를 세고 그 갯수가 Pn에 나오는 n과 일치하면 한번 찾은 것으로 간주한다. 도대체 이런 생각은 어떻게 하는 거냐 ㅡㅡ

전체적인 로직은 위에 적힌 말을 이해하면 훨씬 간단하게 코드로 작성할 수 있다. 반대로 아래 코드가 이해된다면 위에 말도 이해가 될 것이다. (사과는 apple, apple은 사과ㅋㅋㅋㅋ)

from sys import stdin

input = stdin.readline


def ioioi(n, m, s):
    pn = 0
    cnt = 0
    i = 1
    while i < m - 1:
        if s[i - 1] == 'I' and s[i] == 'O' and s[i + 1] == 'I':
            pn += 1
            if pn == n:
                cnt += 1
                pn -= 1
            i += 2
        else:
            pn = 0
            i += 1
    return cnt


if __name__ == "__main__":
    N = int(input())
    M = int(input())
    S = input().strip()
    res = ioioi(N, M, S)
    print(res)

포스팅을 또 한창 안한티가 나네.. 제출한 시간이..

'Algorithm > 백준(BOJ)' 카테고리의 다른 글

[Python] 7569 - 토마토  (0) 2021.03.10
[Python] 6064 - 카잉 달력  (0) 2021.03.10
[Python] 5430 - AC  (0) 2021.03.10
[Python] 11723 - 집합  (0) 2021.03.10
[Python] 1074 - Z  (0) 2021.02.14