Algorithms
백준 16139. 인간-컴퓨터 상호작용
Brian Go
2022. 7. 12. 01:19
https://www.acmicpc.net/problem/16139
16139번: 인간-컴퓨터 상호작용
첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째
www.acmicpc.net
문제
승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다.
'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'
승재를 도와 특정 문자열 S, 특정 알파벳 α와 문자열의 구간 [l,r]이 주어지면 S의 l번째 문자부터 r번째 문자 사이에 α가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 0번째부터 세며, l번째와 r번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 q번 할 것이다.
해결
문자열의 0번째부터 i번째까지의 합을 저장하는 이중 배열을 만들고, e번째 합에서 l-1번째 합을 뺄 생각을 했고 구현했다.
67퍼센트에서 한참 멈춰 있다가 50점밖에 채점이 되지 않길래, 시간 문제라고 판단하고 sys.stdin.readline을 이용하니 해결되었다.
import sys
input = sys.stdin.readline
s = input()
q = int(input())
l = len(s)
lst = [ [0 for _ in range(128)] for _ in range(l) ]
lst[0][ord(s[0])] = 1
for i in range(1, l):
lst[i][ord(s[i])] = 1
for j in range(ord('a'), ord('z') + 1):
lst[i][j] += lst[i-1][j]
for _ in range(q):
inpt = list(input().split())
c, start, end = inpt[0], int(inpt[1]), int(inpt[2])
if start > 0:
print(lst[end][ord(c)] - lst[start-1][ord(c)])
else:
print(lst[end][ord(c)])