사용자 도구

사이트 도구


ps:problems:boj:16139

인간-컴퓨터 상호작용

ps
링크https://www.acmicpc.net/problem/16139
출처BOJ
문제 번호16139
문제명인간-컴퓨터 상호작용
레벨실버 1
분류

누적합

시간복잡도O(n + q)
인풋사이즈n<=200,000, q<=200,000
사용한 언어Python
제출기록79192KB / 708ms
최고기록580ms
해결날짜2022/05/31
태그

[라이] 구간합 배열

풀이

  • 부분합 쿼리 문제. 알파벳별로 누적합을 각각 만들어주고 쿼리에서 물어보는 알파벳의 누적합에서 계산해주면 된다.
  • 누적합을 최대 26개 만들어야 하니까 O(|S|*26)이 걸리고, 쿼리는 각 쿼리당 O(1) 에 처리가능하다. 알파벳의 갯수 26을 상수로 보면, O(|S| + q).

코드

"""Solution code for "BOJ 16139. 인간-컴퓨터 상호작용".

- Problem link: https://www.acmicpc.net/problem/16139
- Solution link: http://www.teferi.net/ps/problems/boj/16139

Tags: [Prefix sum]
"""

import sys


def main():
    S = sys.stdin.readline().rstrip()
    prefix_sums = {}
    for c in set(S):
        prefix_sums[c] = ([ps := 0] +
                          [ps := (ps + 1 if c == s_i else ps) for s_i in S])
    q = int(sys.stdin.readline())
    for _ in range(q):
        alpha, l, r = sys.stdin.readline().split()
        try:
            psum = prefix_sums[alpha]
            print(psum[int(r) + 1] - psum[int(l)])
        except KeyError:
            print('0')



if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q O P P Y
 
ps/problems/boj/16139.txt · 마지막으로 수정됨: 2022/05/31 14:23 저자 teferi