143. 16139(인간-컴퓨터 상호작용) - 파이썬

import sys
input = sys.stdin.readline

S = list(input().strip())
q = int(input())
result = ""

alpSum = []
alphabet = [0]*26

for val in S:
        alphabet[ord(val) - 97] += 1
        # 카운팅 정렬 소스
        alpSum.append(alphabet[:])

for _ in range(q):
    a,l,r = input().split()
    l = int(l)
    r = int(r)    
    tmp = 0
    
    tmp = alpSum[r][ord(a) - 97]    
    if l != 0:
        tmp -= alpSum[l-1][ord(a) - 97]
        # 누적합이기 때문에 -1
    result += str(tmp) + "\n"
    
print(result)

문제요약

문자열에서 정해진 구간에 특정 문자가 몇개 있느냐?

설명

단순히 들어온 케이스마다 반복문으로 문제를 푼다면 100점을 맞을 수 없다.

 

카운팅정렬과 비슷하게 알파벳 26개를 지니는 배열을 정의하고 문자열의 각 문자에 대해 인덱스 값을 증가시켜 주어 처리한다.

 

글 만으로는 이해가 어려우니 표를 보자.

다음과 같이 seungjaehwang이 들어왔을 때, 각 문자에 해당되는 index는 위와같은 배열을 갖고 있다.

 

for val in S:
        alphabet[ord(val) - 97] += 1
        # 카운팅 정렬 소스
        alpSum.append(alphabet[:])

이 코드를 통해서 위와같은 표를 만들 수 있는 것이다.

(파이썬에서 list[:] 는 리스트의 전체값을 넣는 다는 뜻이다.)

 

for _ in range(q):
    a,l,r = input().split()
    l = int(l)
    r = int(r)    
    tmp = 0
    
    tmp = alpSum[r][ord(a) - 97]    
    if l != 0:
        tmp -= alpSum[l-1][ord(a) - 97]
        # 누적합이기 때문에 -1
    result += str(tmp) + "\n"

본격적으로 입력값에 대한 처리를 한다.

a는 문자 , l은 시작 구간, r은 끝 구간이다.

끝구간(r)에 입력 받은 문자(a) 의 인덱스에 해당되는 값을 가져온다.

 

주의) 0부터 처리한것이다. 만약 시작구간이 0번째가 아니라면 시작위치를 -1로 해준다.(누적합)