16139번: 인간-컴퓨터 상호작용
첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째
www.acmicpc.net
문제
승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다.
'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'
승재를 도와 특정 문자열 , 특정 알파벳 와 문자열의 구간 이 주어지면 의 번째 문자부터 번째 문자 사이에 가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 번째부터 세며, 번째와 번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 번 할 것이다.
입력
첫 줄에 문자열 가 주어진다. 문자열의 길이는 자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 가 주어지며, 문제의 수는 을 만족한다. 세 번째 줄부터 번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 와 를 만족하는 정수 가 공백으로 구분되어 주어진다.
출력
각 질문마다 줄을 구분해 순서대로 답변한다. 번째 줄에 의 번째 문자부터 번째 문자 사이에 가 나타나는 횟수를 출력한다.
서브태스크 1 (50점)
문자열의 길이는 자 이하, 질문의 수는 개 이하이다.
서브태스크 2 (50점)
추가 제한 조건이 없다.
코드
import sys
input = sys.stdin.readline
s = input().rstrip()
acc = [[0] * 26 for _ in range(len(s)+1)]
for i in range(1, len(s)+1):
for j in range(26):
acc[i][j] = acc[i-1][j]
acc[i][ord(s[i-1])-97] += 1
q = int(input())
for _ in range(q):
a, l, r = input().split()
l, r = int(l), int(r)
print(acc[r+1][ord(a)-97]-acc[l][ord(a)-97])
acc 배열에는 문자열 s의 i(1 ≤ i ≤ 문자열길이)번째 문자까지 각 알파벳의 개수들이 저장된다.
미리 구한 알파벳 개수의 누적합이 있다면 질문이 들어올 때 빠르게 계산하여 출력할 수 있다.
'문제풀이 > 누적합' 카테고리의 다른 글
[Python/파이썬] 백준 10713번 기차 여행 (1) | 2023.10.17 |
---|---|
[Python/파이썬] 백준 13422번 도둑 (0) | 2023.09.02 |
[Python/파이썬] 백준 20440번 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 (0) | 2023.07.04 |
[Python/파이썬] 백준 10986번 나머지 합 (0) | 2023.07.02 |
[Python/파이썬] 백준 21758번 꿀 따기 (0) | 2023.05.24 |