[백준, python] 16139번 - 인간 - 컴퓨터 상호작용

백준 문제풀이 시작

---

문제

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

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

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

입력

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

출력

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

---

풀이

풀이 확인하기

해당 문제를 풀면서 알파벳을 입력받았을 떄 얼마나 있는지 문자열을 그때그때 전부 순회하여 찾으면 O(N)의 시간이 걸리게 된다. 그러므로 좀 더 빠르게 계산을 하는 방법이 필요한데, 누적합을 사용하면 계산을 O(1) 시간 내에 계산할 수 있다.

누적합을 구하기 위해 배열을 하나 만든다. 그리고 배열에서 문자열을 순회하며 해당 알파벳이 나올 때마다 1씩 더해 계속 append 해준다. 그러면 몇번째 글자까지 해당 알파벳이 얼마나 나왔는지 알 수 있을 것이다.

하지만 문제에서는 특정 구간을 구해야 하는데, 이때 예를 들어 A[i, j]를 구하고 싶다면 누적합 배열을 B라 가정하면 B[j+1] - B[i]를 계산해주면 바로 구할 수 있다.

import sys
input = sys.stdin.readline

string = list(input().rstrip())
num = int(input())
ans = {}

for i in range(97, 123):
    temp = 0
    sum = [0]
    for j in string:
        if(chr(i) == j):
            temp += 1
        sum.append(temp)
    ans[chr(i)] = sum

for _ in range(num):
    inp = input().rstrip().split(' ')
    sys.stdout.write(str(ans[inp[0]][int(inp[2])+1] - ans[inp[0]][int(inp[1])]) + '\n')

• baekjoon
• python