ABC 328 C번 복기 - 문자열에서 누적합을 떠올려야 할 때

1. 문제

 

C - Consecutive (atcoder.jp)

C - Consecutive

 

 

2. 풀이

 

매번 부분 문자열을 찾고, 거기서 연속해서 발생하는 문자의 수를 찾으면 당연히 시간초과가 날 것인데,

 

주어진 문자열에서 0번부터 어떤 위치 i까지 나타나는 연속해서 발생하는 문자의 개수를 누적합 배열로 미리 구해놓는다

 

예를 들어 mississippi라고 한다면, count = [0]*(n+1), before = ''으로 초기화해두고,

 

i = 1부터 n까지 순회해서, s[i-1]과 before가 서로 같다면 연속해서 문자가 발생했으니 counting해준다

 

i = 1이면 before = '', s[i-1] = m이므로 서로 다르니 count = [0,0,...]이고 before = m으로 해준다.

 

i = 2이면 before = m, s[i-1] = i이고 서로 다르니 count = [0,0,0,...]이고 before = i

 

i = 3이면 before = i, s[i-1] = s이고 서로 다르니 count = [0,0,0,0,...]이고 before = s

 

i = 4이면 before = s, s[i-1] = s이고 서로 같으므로 count[i] += 1해주고 count = [0,0,0,0,1,...]이며 before = s

 

i = 5이면 before = s, s[i-1] = i이고 서로 다르니 count = [0,0,0,0,1,1,...]이고 before = i

 

...

 

이런식으로 해주면 count = [0,0,0,0,1,1,1,2,2,2,3,3]

 

그렇게 한다면, query로 [l,r]이 주어질때 count[r] - count[l]로 모든 정답을 O(1)에 바로 구할 수 있다.

 

예를 들어 l = 3이고 r = 9이면 s = ssissip인데, 실제로 ss가 2개 있으므로 정답은 2인데 count[9] = 2이고 count[3] = 0이므로,

 

count[9] - count[3] = 2로 구할 수 있다.

 

n,q = map(int,input().split())

s = input()

count = [0]*(n+1)

before = ''

#0~i번 위치까지 존재하는 2번 연속하는 문자의 개수를 count[i]
#누적해서 미리 구해놓는다
for i in range(1,n+1):
    
    if before == s[i-1]:
        
        count[i] += 1
    
    before = s[i-1]
    count[i] += count[i-1]

#[l,r]이 주어질때 해당 부분문자열에서 2번 연속하는 문자의 개수는...
#count[r] - count[l]로 바로 구할 수 있다
for _ in range(q):
    
    l,r = map(int,input().split())

    print(count[r] - count[l])