[🥈1 / 백준 16139 / 파이썬] 인간-컴퓨터 상호작용

 

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

 

문제

승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. 

'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'

승재를 도와 특정 문자열 S, 특정 알파벳 α와 문자열의 구간 [l,r]이 주어지면 S의 l번째 문자부터 r번째 문자 사이에 α가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 0번째부터 세며, l번째와 r번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 q번 할 것이다.

입력

첫 줄에 문자열 S가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 q가 주어지며, 문제의 수는 1≤q≤200,000을 만족한다. 세 번째 줄부터 (q+2)번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 α_i와 0≤l_i≤r_i<|S|를 만족하는 정수 l_i,r_i가 공백으로 구분되어 주어진다.

출력

각 질문마다 줄을 구분해 순서대로 답변한다. i번째 줄에 S의 l_i번째 문자부터 r_i번째 문자 사이에 αi가 나타나는 횟수를 출력한다.

서브태스크 1 (50점)

문자열의 길이는 2,000자 이하, 질문의 수는 2,000개 이하이다.

서브태스크 2 (50점)

추가 제한 조건이 없다.

 

예제 입력 seungjaehwang 4 a 0 5 a 0 6 a 6 10 a 7 10

예제 출력 0 1 2 1

 

풀이

 

범위를 입력받을 때마다 문자의 처음부터 끝까지 알파벳의 개수를 센다면 O(N^2)이 된다.

1억번 연산에 보통 1초가 소요된다고 하는데, 200,000^2 는 400억이므로 시간 초과가 발생하게 된다.

따라서 문자열의 길이만큼 해당하는 dp 배열을 만들고 해당 구간까지의 알파벳이 총 몇 개였는지 세둘 것이다.

그 후, 입력받는 범위의 알파벳 개수를 arr[r] - arr[l-1]로 O(1)로 구한다.

 

import sys
input = sys.stdin.readline

s = input().rstrip()
arr = [[0]*26]
arr[0][ord(s[0])-97] = 1
for i in range(1,len(s)):
    arr.append(arr[-1][:])
    arr[i][ord(s[i])-97] += 1

for _ in range(int(input())):
    c,start,end = list(input().split())
    start,end = map(int,[start,end])
    if start == 0:
        print(arr[end][ord(c)-97])
    else:
        print(arr[end][ord(c)-97]-arr[start-1][ord(c)-97])