[백준/Python] (S1) 5525 - IOIOI

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

 

IOIOI 성공서브태스크다국어

한국어   

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

40473

11326

9218

29.736%

문제

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	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

예제 입력 1 복사

1
13
OOIOIOIOIIOII

예제 출력 1 복사

4

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

예제 입력 2 복사

2
13
OOIOIOIOIIOII

예제 출력 2 복사

2

• OOIOIOIOIIOII
• OOIOIOIOIIOII

---

서브 테스크가 있는 문제다.

기본적으로 생각을 하면 n에 따라서 IOI 배열이 만들어진다고 생각 할 수 있다.

1 = IOI

2 = IOIOI

3 = IOIOIOI ....

따라서 첫번째 풀이는 다음과 같이 풀었다.

# 5525 IOIOI 
import sys

n = int(sys.stdin.readline())
ioi = ''
for i in range(1, n * 2 + 2): # n이 1이라면 4, n이 2라면 6, 1에서 n*2+2 까지니까 즉 수는 n*2+1까지 나온다.
    if i % 2 == 1:
        ioi += 'I'
    else:
        ioi += 'O'
m = int(sys.stdin.readline()) # s의 길이
s = sys.stdin.readline() #주어진 문자열

count = 0 # 동일한 문자열이 나온 갯수

for i in range(m-len(ioi)+1):
    if s[i:i+len(ioi)] == ioi:
        count += 1
        
print(count)

n에 입력된 수만큼 IOI를 만들어 주고, 문자열을 잘라가면서 IOI의 갯수를 세 주었다.

이렇게 풀었더니 서브테스크 1번만 맞고 2번부터는 시간초과가 떴다.

 

예를 들어서 n이 1000000정도로 입력이 되면 위의 코드에선 IOI배열을 만들기 위해 1000000q번 돌아가고 거기에 ioi+='I'와 같은 연산을 실행하기 위해 또 추가적인 연산이 필요하게 된다.

 

ioi += 'I' 와 같은 연산은 일단 ioi를 한번 더 복사해와야하기 때문에 연산의 길이가 어마어마해진다.

 

이 문제를 해결하기위해 질문 게시판을 찾던 중 라빈코프 알고리즘을 찾았다.

 

라빈코프 알고리즘이란, 문자열을 검색하기 위한 알고리즘으로 검색할 문자열이 길면 길수록 속도가 빨라진다는 장점이 있었다.

기본적인 연산은 각 자리의 해시코드를 다 더해 문자열을 비교할때 해시코드를 사용하여 비교한다.

단, 해시코드가 같을때 해시코드만 같고 문자열은 다를 수 있기 때문에 문자열을 한번 더 검사해줘야한다.

https://yjg-lab.tistory.com/218

[알고리즘] 라빈-카프 알고리즘 (Rabin-Karp)

라빈카프 알고리즘에 대한 설명은 위 블로그를 참고하면 된다.

 

이 알고리즘을 적용시켜서 다음과 같이 풀었다.

# 5525 IOIOI 
import sys

def RabinKarp(length, arr): #라빈카프 알고리즘 적용
    R_hash = 0
    for i in range(length): #0~2까지
        if arr[i] == 'O': 
            R_hash += 79 * (2 ** (length-1 - i))
        else:
            R_hash += 73 * (2 ** (length-1 - i))
    
    return R_hash

n = int(sys.stdin.readline())
ioi = ''.join('I' if i % 2 == 0 else 'O' for i in range(2*n+1))

i_hash = RabinKarp(len(ioi), ioi)

m = int(sys.stdin.readline()) # s의 길이
s = sys.stdin.readline() #주어진 문자열

count = 0 # 동일한 문자열이 나온 갯수
s_hash = 0 #이전 해시값을 저장할 변수

for i in range(m-len(ioi)+1):
    if i == 0: #해시값을 처음으로 찾는다.
        s_hash = RabinKarp(len(ioi), s[i:i+2*n+1])
    else: #이전 해시값에서 계산
        pre_hash = 79 if s[i-1] == 'O' else 73
        next_hash = 79 if s[i+len(ioi)-1] == 'O' else 73
        
        s_hash = (s_hash - (pre_hash * (2**(len(ioi)-1)))) * 2 + next_hash
        
    #비교 시작
    if i_hash == s_hash: #해시값이 같다면 문자열이 달라도 해시값이 같을 수 있기 때문에
        if s[i:i+len(ioi)] == ioi:#문자열 자체를 한번 더 비교
            count += 1
        else:
            continue
    else:
        continue
        
print(count)

일단 IOI를 만드는 과정을 한줄로 줄였는데 다시 생각해보니 저렇게 한다 해도 for문이 돌아가서 반복의 수가 많을 때 그만큼 더 걸리게 되기 때문에 시간복잡도가 여전히 느리다.

 

해시값을 매번 검사해야되는 부분과 IOI배열을 만드는 부분에서 시간이 많이 걸리는것 같아 생각을 달리 했다.

 

IOI 배열을 만들 때, 규칙을 살펴보면

IOI

IOIOI 

처럼 같은 문자열이 반복되고

[0:3]과 [2:5]가 같다. 

더 늘어나면 늘어날수록 이 규칙은 성립하기 때문에 최종적으로 문제를 다음과 같이 풀었다.

# 5525 IOIOI 
n = int(input())
m = int(input())
s = input()

answer, i, count = 0,0,0

while i < m-1:
    if s[i:i+3] == 'IOI':#처음 IOI를 찾았다면
        i += 2 #두칸 띄어넘기 왜냐면 IOIOI일때 인덱스가 3:5일경우에도 IOI이기 때문
        count += 1 #찾았으니 카운트 세줌
        if count == n: #IOI의 갯수가 n개라면
            answer += 1 #정답에 1 추가
            count -= 1 #IOI가 겹쳐 있는 경우도 있으니깐 이어서 세 주기 위해 1 빼줌
            
    else: #못찾았다면
        i += 1
        count = 0
    
print(answer)