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

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

16139번: 인간-컴퓨터 상호작용

처음 이 문제를 봤을 때 범위만큼 문자열을 잘라서 입력받은 문자의 개수를 세주면 되겠다고 생각했지만 실버 1인데 그렇게 간단할 리가 없다고 생각해 누적합을 사용해 보기로 했다.

 

a~z까지 리스트를 처음 문자열의 길이만큼 만드면 i 번째에 있는 a~z까지의 리스트의 숫자는 0~i번째까지 나온 횟수이다. 처음에는 2차원 배열의 크기가 커 메모리 초과 날것을 대비해 python3로 제출했으나 50점을 받아 pypy로 제출했더니 100점을 받았다.

*메모리 크기 계산 방법을 공부해야겠다.*

import sys
input = sys.stdin.readline
s = input()
n = int(input())
re = [[0]*26 for i in range(len(s))]
for i in range(len(s)):
    for j in range(26):
        if ord(s[i])-97==j:
            re[i][j] = re[i-1][j]+1 #한번 나왔으니 누적합 +1
        else:
            re[i][j] = re[i-1][j]#안 나왔으니 누적합
for _ in range(n):
    t,x,y = input().split()
    if int(x)==0:
        print(re[int(y)][ord(t)-97])#0~y번째까지니 그냥 [y]를 출력해주면 된다.
    else:
        print(re[int(y)][ord(t)-97]-re[int(x)-1][ord(t)-97])#x~y까지이니 [y]-[x-1]를 출력해주면 된다.