1. 문제

출처: 백준 16139번 인간-컴퓨터 상호작용

2. 풀이

알파벳의 아스키코드와 DP를 이용하는 문제이다.

알파벳 소문자 a~z는 97~122의 아스키코드 숫자로 표현된다.
Python에서는 ord()를 이용하면 된다.

문자열을 쭉 읽으면서 각 알파벳 소문자가 몇 개 포함되어 있는지 DP 방식을 이용하여 저장하고, 원하는 구간의 값을 출력하면 된다.

Python 3로 제출할 시 시간 초과가 발생하기 때문에, PyPy3으로 제출해야 한다.

3. 소스코드

import sys

input = sys.stdin.readline

words = input().strip()
q = int(input())
n = len(words)
dp = [[0]*26 for _ in range(n)]
dp[0][ord(words[0])-97] = 1
for i in range(1,n):
    dp[i][ord(words[i])-97] = 1
    for j in range(26):
        dp[i][j] += dp[i-1][j]
        
for _ in range(q):
    al,l,r = input().split()
    l = int(l)
    r = int(r)
    al_index = ord(al)-97
    if l > 0:
        print(dp[r][al_index]-dp[l-1][al_index])
    else:
        print(dp[r][al_index])

4. 그 외

처음에 문제를 접했을 때에는, 아스키코드를 떠올리지 못해서 알파벳 리스트를 만들고 비교하는 식으로 구현했었다. 비교하는 과정 때문인지 시간 초과가 발생해서 다른 분들의 풀이를 참고하여 아스키코드 방식을 찾게 되었다.

지금은 list로 구현했는데, dictionary로도 구현이 가능할지 뒤에 해보면 좋을 것 같다.