백준 16139 인간-컴퓨터 상호작용

Intro

Solution

주어진 문자열에 특정한 알파벳이 몇 개 들어있는지 구하는 문제다.

질문이 최대 200,000개 주어지며 알파벳이 중복으로 주어질 수 있기 때문에 누적 합을 이용해서 시간복잡도를 줄여야 한다.

주어진 질문의 알파벳이 처음 나왔다면, 문자열을 순회하며 해당 문자열 개수의 누적 합을 저장한다.

python으로 실행할 때 제한 시간을 통과하지 못했으나, pypy3으로는 통과할 수 있었다.

Code

import sys
input = sys.stdin.readline

def solve():
	S = input().strip()
	size = len(S)
	q = int(input())
	psum = {}

	for _ in range(q):
		a, l, r = input().split()
		l, r = int(l), int(r)
		if a not in psum:
			psum[a] = [0]
			[psum[a].append(psum[a][i-1] + (a==S[i-1])) for i in range(1, size+1)]
		print(psum[a][r+1] - psum[a][l])

solve()