백준 - 16139번(누적합)

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

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

 

50점 답안

import sys

s = list(sys.stdin.readline().rstrip())

t = int(sys.stdin.readline())

for k in range(t):
    tmp = [0 for _ in range(len(s))]
    cache = 1

    a,l,r = sys.stdin.readline().split()

    l = int(l)
    r = int(r)

    for i in range(len(s)):
        if s[i] == a:
            if i == 0:
                tmp[0] = 1
            else:
                tmp[i] = tmp[i-1] + 1
        else:
            tmp[i] = tmp[i-1]

    if l == 0:
        print(tmp[r])
    else:
        print(tmp[r] - tmp[l-1])

위의 방식은 부분점수로 50점을 받은 답안이다.

알고리즘은 시간과 메모리의 밸런스 싸움이라고 할 수 있다.

 

메모리를 많이 쓸 수 있으면 시간을 줄일 수 있고, 반대로 메모리가 여의치 않다면 시간 복잡도를 늘려야 한다.

 

100점 답안

import sys

s = list(sys.stdin.readline().rstrip())

t = int(sys.stdin.readline())

ans = [[0 for _ in range(26)] for _ in range(len(s))]

for i in range(len(s)):
    if i == 0:
        ans[i][ord(s[i])-97] = ans[i][ord(s[i])-97] + 1
    else:
        for j in range(26):
            ans[i][j] = ans[i-1][j]
        ans[i][ord(s[i]) - 97] = ans[i][ord(s[i]) - 97] + 1


for k in range(t):
    a,l,r = sys.stdin.readline().split()

    key = ord(a)-97

    l = int(l)
    r = int(r)

    if l > 0:
        print(ans[r][key] - ans[l-1][key])
    else:
        print(ans[r][key])

각 문자를 ASCII 코드로 바꿔서 26 * len(s) 크기의 2차원 배열에 각각 맵핑해 준다.

반복문을 실행하면서 누적합을 만들어 간다.

 

마지막은 조건에 맞게 출력한다.