[Baekjoon]백준 16139 인간-컴퓨터 상호작용(실버 1) - Python

문제설명 1

문제설명 2

문제를 살펴보면 어떠한 문자열을 입력받게되고, 특정 문자열이 입력받은 index안에 몇개 존재하는지 출력하는 문제이다

즉, abacaba 라는 문자열이 있을 때, a 0 4 라고 입력을 받으면

첫번째 index부터 4번째 index까지 a가 몇개 있는지 출력해야한다(해당 예시에서는 3이 출력될 것이다)

문제를 자세히 살펴보면 하나의 문자에 대해서 질문을 반복하기 때문에 질문을 할때마다

index 범위에 따른 개수를 저장하는 것보다 미리 값들을 저장한 리스트를 만들어두고 값을 꺼내오는게 더 간단하다

 

그래서 하나의 딕셔너리를 만들어 등장하는 문자열을 저장하도록 하였다

해당 문자열의 길이만큼 0을 만들어주고 등장하는 문자열의 위치에 1을 넣어준다

문자열 s = "abacaba"라면:
count['a'] = [1, 0, 0, 1, 0, 1, 1]
count['b'] = [0, 1, 0, 0, 1, 0, 0]
count['c'] = [0, 0, 1, 0, 0, 0, 0]

이후 누적 합 알고리즘을 이용하여 해당 딕셔너리를 최신화 시켜준다

이 딕셔너리에는 이제 0번부터 i번째 index까지 해당 알파벳의 등장 횟수를 저장하게 된다

예시 : 
count['a'] = [1, 1, 1, 2, 2, 3, 4]
count['b'] = [0, 1, 1, 1, 2, 2, 2]
count['c'] = [0, 0, 1, 1, 1, 1, 1]

이후에는 각 index까지의 등장횟수를 출력하면 되는데, 시작점이 0인 경우 start - 1이 index를 벗어나기 때문에

if문을 이용하여 따로 정의하여 주어야한다

0이 아니라면 end_index에 저장된 값에서 start_index - 1에 저장된 값을 빼주면 된다

(start_index의 값을 빼면 start_index의 값은 고려하지 않은 것이 되므로 -1한 index의 값을 빼주어야한다)

만약 해당 알파벳이 딕셔너리에 존재하지 않는다면 0을 출력해주면 된다

※참고 ※

python3로 제출하게 되면 시간초과가 발생하기 때문에 PyPy3로 제출하여야 100점을 받을 수 있다

import sys

letter = input()
num = int(input())
result = {}

# 등장하는 문자의 누적 합 딕셔너리 생성
for i, char in enumerate(letter):
    if char not in result:
        result[char] = [0] * len(letter)
    result[char][i] = 1
    
# 누적 합 계산
for char in result:
    for i in range(1, len(letter)):
        result[char][i] += result[char][i-1]

# 결과값 출력 
for _ in range(num):
    alpha, start_index, end_index = sys.stdin.readline().split()
    start_index, end_index = int(start_index), int(end_index)
    if alpha in result:
        if start_index:
            print(result[alpha][end_index] - result[alpha][start_index-1])
        else:
            print(result[alpha][end_index])
    else:
        print(0)

다른 분들의 풀이를 참고한 결과, 아스키코드로 변환하여 계산하는 코드를 작성하면 Python으로 제출하여도 되는듯하다