16139번: 인간-컴퓨터 상호작용 / silver 1 / 누적합, ord()

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

16139번: 인간-컴퓨터 상호작용

 

50점 정답

'''
16139번: 인간-컴퓨터 상호작용 / silver 1 
'''
import sys

input = sys.stdin.readline

s = input().rstrip()
q = int(input())
for _ in range(q):
    alpha, start, end = input().split()
    start, end = int(start), int(end)
    cnt = 0
    for i in range(start, end + 1):
        if s[i] == alpha:
            cnt += 1
    print(cnt)

 

100점 정답

'''
16139번: 인간-컴퓨터 상호작용 / silver 1 / 누적합
'''
import sys

input = sys.stdin.readline

s = input().rstrip()
q = int(input())
# 누적합 담을 arr 만들기
arr = [[0 for _ in range(26)] for _ in range(len(s))]
arr[0][ord(s[0]) - 97] = 1
for i in range(1, len(s)):
    for j in range(26):
        arr[i][j] += arr[i - 1][j]
    arr[i][ord(s[i]) - 97] += 1
# 누적합 이용하여 결과값 출력
for _ in range(q):
    alpha, start, end = input().split()
    start, end = int(start), int(end)
    if start == 0:
        print(arr[end][ord(alpha) - 97])
    else:
        print(arr[end][ord(alpha) - 97] - arr[start - 1][ord(alpha) - 97])

 

Review

 

100점을 맞으려면,

매우 긴 문자열이 입력 받고 (최대 200,000자) / 많은 문제의 수 (최대 200,000) 를 처리해야 한다.

 

50점의 정답 코드를 보면,

start ~ end 인덱스를 하나하나  확인 것을 * q 만큼 진행한다.

따라서 최악의 경우,

start~end 사이 확인 200,000 * q문제의 수 200,000 = O(40,000,000,000) 시간 복잡도를 가진다.

 

해결 방법

누적합을 이용하여 start~end 사이 확인하는 반복을 없애기

(100점 코드 및 주석 보기)

100점 코드 시간 복잡도

- len(s) * 26 +  q

- 최악의 경우, 200,000 * 26 + 200,000 = O(200,000 * 27)