[백준]5525번: IOIOI(Python)

2022-06-03 3 분 소요

IOIOI

solved_ac[Class3] IOIOI

문제

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

P1 IOI
P2 IOIOI
P3 IOIOIOI
Pn IOIOI…OI (O가 N개)

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

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

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

제한

1 ≤ N ≤ 1,000,000
2N+1 ≤ M ≤ 1,000,000
S는 I와 O로만 이루어져 있다.

서브태스크

예제 입력 1

1
13
OOIOIOIOIIOII

예제 출력 1

예제 입력 2

2
13
OOIOIOIOIIOII

예제 출력 2

문제 해석

예를 들어 OOIOIOIOIIOII 라는 문자열을 입력을 받았고 N = 1을 입력을 받았다면 일단 N = 1인 문자열이 무엇인지 생각해야한다.

N = 1 : P1 = “IOI”
N = 2 : P2 = “IOIOI”
N = 3 : P3 = “IOIOIOI”

이런 규칙이 나오게 되는데 여기서 생각하야 할 것은 N = 1일 때 IOI가 한 번 나오고 N = 2일 때 IOI가 두 번 나오는 것이다. IOIOI에서 왜 IOI가 두 번일까? IOI가 한번 나오고 나서 다시 I에서 시작해서 IOI를 새는 것이다. 이렇게 생각하고 나서 풀이를 생각하면 쉽게 풀 수 있다.

풀이

첫 번째 풀이

[50점]

예시)N = 1, 2N + 1 = 13, S = "OOIOIOIOIIOII"

슬라이싱 이용
Pn에 맞는 문자열 넣어주기 Pn += "I" or += "O"
IOI를 S에서 발견하면 index를 2만큼 증가 후 다시 슬라이싱을 이용해서 Pn의 나머지 부분과 compare_str을 비교
다 비교해서 Pn이 compare_str안에서 발견이 되면 count를 + 1 해줌
만약 비교해서 아니면 어차피 index를 기준으로 슬라이싱 하기 때문에 순차적으로 다른 Pn을 찾을 수 있음.

여기서 50점이 뜬 이유는 슬라이싱 때문이다. 슬라이싱의 시간 복잡도는 list[a:b}이면 O(b-a)의 시간 복잡도가 나오게 된다.

이 슬라이싱을 이중으로 사용하기 때문에 이중 for문과 다를게 없어서 범위가 많아지게 되면 시간초과가 뜨는 것이다.

코드

import sys

N = int(sys.stdin.readline())
length = int(sys.stdin.readline())
compare_str = sys.stdin.readline()

Pn = ""

for i in range(2 * N + 1):
    if i % 2 == 0:
        Pn += "I"
    else:
        Pn += "O"
index = 0
count = 0

while True:
    if compare_str[index:index+3] == "IOI":
        index += 2
        if N == 1:
            count += 1
        else:
            a = index +  len(Pn) - 2
            if compare_str[index+1:a] == Pn[3:]:
                count += 1
    else:
        index += 1
    if index == (length - 2):
        break
    
print(count)

두 번째 풀이

[맞는 풀이]

위의 풀이에서는 슬라이싱을 이중으로 사용하기 때문에 시간 초과로 인해 점수가 50점 밖에 받지 못하였다. 그래서 IOI를 찾는 슬라이싱과 나머지 Pn을 찾는 슬라이싱까지 없애고 다르게 코딩을 하였다.

IOI를 찾을 때, 슬라이싱이 아닌 index를 기준으로 index - 1, index, index + 1로 IOI를 찾았다.
IOI를 찾으면 index는 2를 증가시켜주면서 다음 IOI를 찾기 위한 준비를 한다.
IOI를 찾을 때마다 count 값을 1씩 증가시켜 준다. 맨 위에 문제 해석에서 말한 것 처럼 IOI의 갯수를 찾는 것이다.
O를 기준 index로 삼아서 검사를 하기 때문에 index를 2 증가 시켜주면 다음 문자열 3개가 IOI라는 가정하에 compare_str[index + 2]는 "O"가 될 것이다.
입력에서 N값을 입력 받았는데 N값은 IOI의 개수라고 생각하면 편하다. 그래서 IOI가 연속으로 나올때마다 count를 1개씩 증가시켜주고 만약 count가 N값과 같으면 result를 +1 해준 후 count를 하나 깎아준다.
여기서 count를 -1 해주는 이유는 계속해서 연속되는 IOI가 나올수도 있기 때문이다. ex)N=2 일때, compare_str = "IOIOIOI" 인 경우이다.
count - 1 연산 덕분에 계속해서 연속되어서 나오는 IOI를 계산해 줄 수 있다.
만약 IOI의 연속이 끊기게 되면 count를 초기화 시켜주고 index를 1만 증가 시켜준다. 바로 다음 index에서 IOI가 나올 수도 있기 때문이다.

코드

import sys

N = int(sys.stdin.readline())
length = int(sys.stdin.readline())
compare_str = sys.stdin.readline()


index = 1
count = 0
result = 0

while True:
    if compare_str[index - 1] == "I" and compare_str[index] == "O" and compare_str[index + 1] == "I":
        index += 2
        count += 1
        if count == N:
            count -= 1
            result += 1
    else:
        index += 1
        count = 0
    if index >= (length - 1):
        break
    
print(result)

Twitter Facebook LinkedIn