[백준] 16139번 인간-컴퓨터 상호작용(feat. 누적 합)

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

 

문제 접근

• 첫 번째 단계

문제의 조건은 다음과 같다.

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

문제를 간단히 요약해 보면, 아래와 같다.

입력으로는
1. 문자열 s(문자열의 길이는 200000자 이하이며 알파벳 소문자로만 구성)
2. 질문의 수 q
3. 이후부터는 질문이 주어지는데, 각 질문은 알파벳 소문자 x와 구간 a이상 b이하 로 주어짐

a <=  <= b 이 구간 사이에 제시된 x가 나타나는 횟수를 출력해야 한다.

문자열의 길이가 최대 20만이므로, 일일이 구간을 확인한다면 너무 비효율적으로 동작할 것으로 예상된다.따라서, 누적 합을 사용해야 할 것이다.

 

• 두 번째 단계

누적 합 리스트를 모든 알파벳에 대해서 고려해야 하기 때문에,
2차원 배열이 필요할 것으로 예상된다. 

이것을 좀더 쉽게 만들 수 있는 방법이 있다.

바로 String 클래스의 ascii_lowercase를 이용하는 방법이다.

print(string.ascii_lowercase)

를 찍어보면, 소문자 알파벳이 출력되는 것을 확인할 수 있다. (uppercase도 있다. 자세한 것은 공식문서를 참고하도록 하자.)

이것을 이용해서 for문으로 각 알파벳을 받아서 dictionary자료형에 'a':[0], 'b':[0] 이런식으로 만들 수 있다.

처음에 char_list 라는 dictionary 자료형을 선언하고,
해당 자료의 키값으로 stirng.ascii_lowercase의 각 알파벳을 받아서 value에 [0]을 저장해주면 된다.

그리고 바로 하나의 알파벳마다 이중 포문을 구성해서 주어진 문자열의 길이만큼 돌면서,
만약에 현재 char이 현재가리키는 문자열의 문자와 같으면, count 라는 변수에 1을 더해주고,
char_list[char].append(count)를 해주면,  a~z까지 쭉 돌면서 현재 문자열에 있는 문자들의 누적합을 각 알파벳을 key로 갖는 각 배열에 갱신해 줄 수 있다.

그리고나서 질문을 입력받고, 그에 해당하는 알파벳이 입력받은 구간에 몇개가 있는지,
앞서 만들어둔 알파벳별 누적합 리스트를 이용하여 계산해서 반환하면 된다.

 

실제로 코드를 작성하기전, 고민한 과정을 공유한다.

'''
입력으로는
1. 문자열 s(문자열의 길이는 200000자 이하이며 알파벳 소문자로만 구성)
2. 질문의 수 q
3. 이후부터는 질문이 주어지는데, 각 질문은 알파벳 소문자 x와 구간 a이상 b이하 로 주어짐

a <=  <= b 이 구간 사이에 제시된 x가 나타나는 횟수를 출력해야 한다.

i)
제일 간단한 방법 먼저 생각을 해보자.
count라는 변수를 만들어서
입력 받은 문자열의 주어진 구간을 돌면서 탐색해야하는 문자가 몇개있는지 세기. -> 이 방법은 50점을 받음

ii)
비효율 적인 부분을 생각해보면, 문자열의 길이가 최대 20만 자리인데,
지금의 알고리즘으로는 각 질문마다 슬라이싱하면서 찾게 되는데,
이때, 만약에 첫번째 질문이 a 0 5 이고,
두번째 질문이 a 0 7 이면 0 5 구간이 겹침에도 불구하고, 두번째 질문을 탐색할 때는 0 7 구간을 탐색하게 되므로 이 부분이 비효율 적일 것이다.

이 비효율적인 것을 개선하려면 어떻게 해야할까?
첫 번째 질문에서 0:5구간을 탐색했으므로, 이것을 저장해놓고,
두 번째 질문을 수행할 때 이용하도록 하면 되지 않을까?

딱 떠오른 아이디어인데,
dp 테이블처럼 누적 되도록 어떤 값을 저장하는 리스트를 만들고,
만약에 첫번째 0:5가 1이라고 가정하면,  해당 구간의 테이블을 1로 채워놓는 방식?

그러면 일단 테이블의 길이를 문자열의 길이와 같게 생성해야 할 것 같다. 만약에 문자열의 길이가 10이면 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 이렇게 생성하고
그다음, a 0 5의 결과가 1이라면 0~5 인덱스(*문제 조건 때문에 5포함임)의 테이블 값을 1로 저장한다.[1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
두번째 질문이 a 0 7이면 6~7만 탐색해서 5의 것을 더하여 갱신하면 된다. 만약에 6~7의 결과가 2라면 [1, 1, 1, 1, 1, 1, 3, 3, 0, 0]
[
ssssasaasss
2
a 0 5
a 0 7
] 이 예제에 대해선 맞는데..

이렇게 짜니까 문제가 있음.
a 0 5
a 0 7 이런 질문에 대해선 잘 맞는데,

a 6 10
a 7 10 이런식으로 중간부터 시작하는 질문에는 안맞음

이 문제는 어떻게 해결해야 할까?

iii)
테이블의 갱신범위를 그냥 딱 1개씩으로 축소해서 다 구해 놓으면 어떨까?

예를 들면, seungjaehwang 문자열에서 a를 탐색한다고 했을 때,
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2) 이런식으로.


iiii)
누적합 리스트를 모든 알파벳에 대해서 고려해야 하기 때문에
2차원 배열로
accum_list = [[0] * len(word) for _ in range(accum_len)]
그런데 이렇게 할 필요 없고,

stirng.ascii_lowercase를 이용해서 소문자를 반환함과 동시에 for문으로 char를 받아서 돌리고,
각 알파벳을 key로 하는 dic을 만드는데, char_list[char] = [0]  이렇게 하면
{'a': [0], 'b': [0], 'c': [0]...
이런식으로 만들어진다.

그리고 이중 for문을 구성하는데, len(s)를 돌도록 하여
if s[i] == char 이면
count = count + 1 이 되도록 하고
char_list[char].append(count)는 if문 밖에서 해주면,
if문을 통과하지 않아도 char_list에 0을 append하게 하여 원하는 형태의 2차원 dic를 만들 수 있다. * dic 사용법 확실히 파악할 것.
'''

 

 

코드 작성

import sys
import string

s = input()
q = int(input())

# 알파벳별 저장
char_list = {}
for char in string.ascii_lowercase:
    char_list[char] = [0]
    count = 0
    for i in range(len(s)):
        if s[i] == char:
            count = count + 1
        char_list[char].append(count)
    print(char_list)

for _ in range(q):
    char, start, end = sys.stdin.readline().rstrip().split()
    start, end = int(start), int(end)
    print(char_list[char][end+1] - char_list[char][start])