[78일차][백준][누적합][16139]인간-컴퓨터 상호작용

문제 설명

 

 

입력

 

 

출력

 

서브태스크 1

 

서브태스크 2

추가 제한 조건이 없다.

 

예제 입력, 예제 출력

seungjaehwang 4 a 0 5 a 0 6 a 6 10 a 7 10

0 1 2 1

 

코드 및 설명

import sys

s = list(sys.stdin.readline())
q = int(sys.stdin.readline())

for idx in range(q):
    a, i, j = sys.stdin.readline().split(" ")
    sum = 0
    for idx in range(int(i), int(j)+1):
        if s[idx] == a:
            sum += 1
            
    print(sum)

 

 

처음 누적합으로 풀어야하는 데 먼저 생각 나는 대로 풀어보았다. 첫번째 줄에 문자열을 받고, 두번째 줄에선 몇 번 반복할지 세번째 줄은 첫번째 인자로 찾을 문자, 최소범위, 최대범위 이렇게 제공된다.

s의 문자열을 담고 q에 반복 실행할 횟수를 담았다. 그다음 q만큼 a, i, j를 반복해서 제공 받는 데 저 위에 코드는 범위에서 a에 해당하는 문자열이 있으면 sum+1해주는 단순 방식이다. 이렇게 되면 모든 범위안을 전부 검사하는 형태가 되어 시간복잡도가 O(n)이 된다. 그러므로, 이 방식은 서브 태스크1은 통과하나 서브태스크 2(아마도 문자열, 질문의 개수가 제한이 없는거 보면 엄청 클것으로 예상.) 통과를 하지 못한다. 이걸 이제 누적합 알고리즘을 이용하여 풀어야한다.

import sys

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

ord_count = 97
alphabet_count = 26
s_arr = [[0] * alphabet_count for _ in range(len(s)+1)]

for i in range(1, len(s_arr)):
    for j in range(alphabet_count):
        if ord(s[i-1])-ord_count == j:
            s_arr[i][j] = s_arr[i-1][j] + 1
        else:
            s_arr[i][j] = s_arr[i-1][j]

q = int(sys.stdin.readline())
for idx in range(q):
    a, i, j = sys.stdin.readline().split(" ")
    a, i, j = ord(a)-ord_count, int(i), int(j)
    print(s_arr[j+1][a]-s_arr[i][a])

 

여러 문제를 풀다보니 뭔가 머리속에 박힌게 문자열이 나오는 데 배열의 위치 혹은 뭔가 정수로 처리해야하는 부분이 나오면 ord(아스키코드로 변환)를 써야하나라는 생각을 하게 되었다. 이 문제도 아스키코드로 변환해서 풀어야한다. 처음 감을 잡지 못하였으나, 검색을 통해 힌트를 얻어 코드를 짤 수 있었다. 

s_arr에 이차원배열을 만드는 데 s문자열의 길이+1만큼 배열을 만들어주고 그 안은 배열은 [0] * 알파뱃 갯수만큼 넣어 이차원 배열을 만들어준다.

a~z까지는 -97를 하게 되면 0~25까지 표현할 수 있다. 그래서 ord(s[i-1]) -> s 문자열에서 0번째 문자를 가져와 아스키코드로 전환하고 그 코드가 현재 0와 같은지 확인한다. 그 다음 같다면 1을 더 해준다. 위에 예제를 설명으로 들자면 a의 문자열의 개수는 14개이다. 누적합에선 0번째부터 쌓는게 아니라 1번째 부터 쌓기 때문에 14+1해서 1차원 배열 공간을 만들어주고, 해당 2차원배열은 알파뱃 개수만큼 공간을 만들어주는 것이다. 그럼 첫번째 문자열인 s를 가져오면 s는 18가 나올 것이고, j가 4가 되는 순간 s_arr[1][18] = s_arr[0][18] + 1를 하게 된다.

[..., [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], ...] 이렇게 쌓이게 된다. 이걸 문자열이 끝날 때까지 반복해주면 

 

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 2, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 2, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 2, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0], [2, 0, 0, 0, 2, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0], [2, 0, 0, 0, 2, 0, 1, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0], [2, 0, 0, 0, 2, 0, 2, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0], [2, 0, 0, 0, 2, 0, 2, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0]]

 

이렇게 만들어 진다. 여기서 이제 q만큼 반복하면서 찾을 문자열 범위를 받는다. s_arr[j+1][a]-s_arr[i][a] -> 만약 'a'라는 문자열을 찾는 다면 a를 아스키코드로 변환하고 -97를 해준다. 그 다음 j = 5, i = 0 이면 s_arr[6][0] - s_arr[0][0]이다. 0 - 0 이므로 0 ~ 5까지 범위 내에는 'a'가 없다. 문자열은 똑같고 범위만  j= 6, i = 0 일땐 s_arr[7][0] - s_arr[0][0] 이다. 1 - 0 이므로 1이다. 0~6까지의 범위 내에 'a'가 한개 있는 것이다. 이런식으로 반복하면 된다.