[백준 16139] 인간-컴퓨터 상호작용 (python)

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

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

인간 - 컴퓨터 상호작용 문제

누적합을 이용해서 문자 α가 범위 내에서 몇번이 나오는지 확인하는 문제

누적 합의 원리로 접근하면 해결 할 수 있는 문제

내가 푼 정답 코드(pypy3로만 통과 가능)

import sys
S = sys.stdin.readline().strip()
q = int(sys.stdin.readline())
alpha = 'abcdefghijklmnopqrstuvwxyz' #알파벳 모음

temp = {} # 누적합을 저장해줄 딕셔너리
for i in alpha: # 각각의 알파벳에 대해
    cnt = 0 
    temp1 = [0]*len(S) # 누적합을 구해보자
    for j in range(len(S)) : # 범위에서
        if i == S[j] : # 알파뱃 등장하면
            cnt += 1 # 횟수 늘리고
        temp1[j] = cnt # 누적해서 temp1에 저장
    temp[i] = temp1 # 알파벳 : 누적합 리스트 형태로 저장

for _ in range(q):
    a, l, r = sys.stdin.readline().split() 
    l, r = int(l), int(r)
    acc_sum = temp[a] # 우리가 찾고자 하는 알파벳의 누적합을 꺼내오자
    if l > 0: # 0이상이면
        print(acc_sum[r] - acc_sum[l-1]) # 유효 범위에서 제일 큰 거 - 제일 작은 거 이전꺼까지
    else: # 0이면
        print(acc_sum[r]) #유효 범위에서 제일 큰 애

📌 문제 접근 포인트

1. 일부 구간에 대해서 단어 α가 원하는 구간 내에서 몇개나 존재하는지 찾기 위한 방법을 생각해보자.
2. 단순히 for문의 range로 해서 r과 l사이의 단어 α의 수를 세어주면, 서브 테스크2의 조건에서 시간초과가 나서 50점밖에 받지 못한다.
3. 단어의 등장 갯수를 구하고싶다 → 단어 α의 누적 합을 이용하면 쉽게 접근할 수 있다.
4. 단어의 경우 최초로 주어지고 그 단어에서 각각의 테스트 케이스로 갯수를 확인하는 과정을 거친다 → 즉, 테스트 케이스에 들어가기 전에 미리 단어의 누적 합의 갯수를 구해주고, 뒤의 케이스는 꺼내서 쓰기만 하면 된다.
5. 각 알파벳 별 누적합을 구해주기 위해서 딕셔너리 형태를 만들어주고, 리스트 형태의 누적합을 만들어서 a: a의 누적합, b: b의 누적합, ··· 의 형태로 구성해주자.
6. 이를 이용해서 테스트 케이스에서 해당 알파뱃에 해당하는 리스트만 딕셔너리에서 꺼내서 바로바로 쓸 수 있다.
7. 이때, 원하는 범위 내에서 값은 0일때는 최대 갯수인 r에 해당하는 값을 반환하면 되고, 나머지 케이스에 대해서는 제일 큰 r에서 제일 작은 l의 이전 누적합까지 빼준것을 출력해주면 원하는 답을 얻을 수 있다.
8. 문제 히든 테스트 케이스가 굉장히 길어서 연산이 엄청 수행되는지 파이썬으로는 1초시간 내에 들어올 수 없었고, pypy3로 수행하면 0.3초정도의 수행시간으로 들어와 서브테스크2까지 만족할 수 있었다.