[백준/실버1] 16139번 인간-컴퓨터 상호작용 | 누적합 | 파이썬 Python

문제

https://www.acmicpc.net/problem/16139

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

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

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

 

입력

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

 

출력

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

 

예제

 

나의 풀이 (실패)

import sys
input = sys.stdin.readline

s = input().rstrip()
q = int(input())

first = list(input().split())
prefix_sum = [0]

for i in range(len(s)):
    if s[i] == first[0]:
        prefix_sum.append(prefix_sum[i] + 1)
    else:
        prefix_sum.append(prefix_sum[i])

print(prefix_sum[int(first[2])+1] - prefix_sum[int(first[1])])

for _ in range(q-1):
    _, l, r = input().split()
    print(prefix_sum[int(r)+1] - prefix_sum[int(l)])

• "같은 문자열을 두고 질문을 q번 할 것이다."라는 설명과 예제를 보고 하나의 알파벳에 대해서만 질문할 것이라고 착각하고 너무 단순하게 풀었다...

 

다른 사람의 풀이

import sys
input = sys.stdin.readline

s = input().rstrip()
q = int(input())

pre = [[0] * 26]

for i, str in enumerate(s):
    next = pre[i][:]
    next[ord(str)-97] += 1
    pre.append(next)

for _ in range(q):
    a, l, r = input().split()
    i = ord(a) - 97
    print(pre[int(r)+1][i] - pre[int(l)][i])

26개의 알파벳에 대해 각각의 문자가 등장하는 누적합을 저장하는 리스트를 만들어 놓고, 

이를 이용해 특정 문자의 출현 횟수를 빠르게 계산한다.

 

2차원 리스트 `pre[i][j]`에 i번째 문자까지 j번째 알파벳의 등장 횟수를 저장한다.

 

예를 들어 문자열 "seungjaehwang"에 대해 `pre[8][ord('a')-97]`은 

8번째 문자열까지인 "seungjae"에 "a"가 몇 번 등장했는지를 나타낸다.

 

알파벳의 인덱스는 해당 문자의 유니코드를 반환하는 `ord()`를 사용해서 구한다.

알파벳 "a"가 97부터 시작하기 때문에 `ord('a')-97`로 계산한다.

 

문자열을 순차적으로 탐색하면서 이전의 누적합이 담긴 리스트를 복사하고

현재 문자의 개수까지 반영한 후 리스트에 추가한다.

 

문자열의 알파벳과 인덱스를 모두 사용하기 위해

인덱스와 값을 묶어서 튜플을 생성하는 `enumerate()`를 사용했다.

또한 리스트를 복사할 때는 깊은 복사를 위해 슬라이싱`[:]`을 사용했다.

 

각 질문에 대해, [l, r] 구간에서 특정 문자 a의 출현 횟수는

`pre[r+1][ord(a)-97] - pre[l][ord(a)-97]`로 구할 수 있다.