[Python] 백준 16139 인간-컴퓨터 상호작용

1. 문제 - 백준 16139 인간-컴퓨터 상호작용

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

 

💡알고리즘 - 구간합 알고리즘

• 문자열의 구간 별 알파벳의 등장 횟수를 구해야하나, 문자열의 길이가 200,000자 인데 질문의 갯수인 q도 200,000개이다.
  매번 반복문을 통해 알파벳의 등장 횟수를 구하면 시간초과가 발생한다.
• 구간 문제의 해답을 구할 때 O(N^2)의 시간복잡도를 O(N)의 시간복잡도로 해답을 구할 수 있도록 해주는 알고리즘이 구간합 알고리즘이다.
• 구간합 알고리즘이란? i ~ j 구간합을 구할 때 누적합을 구해두고 -> arr[i] - arr[j-1] 의 공식을 통해 구간합을 구하는 방식이다.

✅ 풀이

import sys
input = sys.stdin.readline

example = input().rstrip()
n = len(example)
arr = [[0] * 26 for _ in range(n)]    # 1)
arr[0][ord(example[0]) - ord('a')] = 1  # 2)

for i in range(1, n):          # 3)
  arr[i][ord(example[i]) - ord('a')] += 1
  for j in range(26):
    arr[i][j] += arr[i-1][j]

q = int(input())
for _ in range(q):
  alpha, start, end = input().split()
  start = int(start)
  end = int(end)
  
  if start == 0:     # 4)
    print(arr[end][ord(alpha)-ord('a')])
  else:
    print(arr[end][ord(alpha)-ord('a')] - arr[start-1][ord(alpha)-ord('a')])

 

ord(알파벳)은 알파벳의 아스키 정수값을 반환해주는 함수이다.

ord(알파벳) - ord('a')를 하게되면 a를 인덱스 0으로 시작해서 현재 알파벳의 인덱스를 반환해준다.

 

1) 주어진 문자열의 길이만큼, 각 인덱스 별로 모든 알파벳의 갯수를 누적합을 구하기 위해 2차원 배열을 설계한다.

2) 누적합을 구하기 전에 첫번째 인덱스의 알파벳의 갯수를 + 1 해준다.

3) 각 인덱스 별로, 인덱스에 해당하는 알파벳의 갯수를 더한다음 문자 별 알파벳의 갯수 누적합을 구한다.

4) start가 0일 경우 누적합이기 때문에 끝 인덱스에 해당하는 누적합을 반환하면 되고, 그게 아니라면 arr[j] ~ arr[i]의 구간합 공식처럼 arr[j] - arr[i-1] 의 값을 반환하면 된다. 

 

마지막으로 input 처리할때 import sys, sys.stdin.readline이 아니라 그냥 input()을 사용하면 67%에서 시간초과가 발생해서 50점으로 나온다.