[백준/Python] 16139 인간-컴퓨터 상호작용

정답 코드 및 설명

전체 코드

# 문자열 입력
string_input = input().strip()

# 쿼리 수 입력
query_count = int(input())

# 누적 합 배열 초기화
cumulative_sums = [[0 for _ in range(26)] for _ in range(len(string_input))]

# 첫 문자에 대한 누적 합 설정
cumulative_sums[0][ord(string_input[0]) - ord('a')] = 1

# 나머지 문자에 대한 누적 합 계산
for index in range(1, len(string_input)):
    cumulative_sums[index][ord(string_input[index]) - ord('a')] = 1
    for char_index in range(26):
        cumulative_sums[index][char_index] += cumulative_sums[index - 1][char_index]
        
# 쿼리 처리
for _ in range(query_count):
    char, start, end = input().split()
    start, end = int(start), int(end)
    # 구간 내 출현 횟수 계산
    if start > 0:
        result = cumulative_sums[end][ord(char) - ord('a')] - cumulative_sums[start - 1][ord(char) - ord('a')]
    else:
        result = cumulative_sums[end][ord(char) - ord('a')]
    # 결과 출력
    print(result)

문제 설명

문자열에서 주어진 구간 내에 특정 문자가 몇 번 등장하였는 지 계산하는 문제이다. 문자열과 쿼리 수 긜고 각 쿼리에 대한 정보(특정 문자와 구간)가 주어진다.

접근법

누적 합 기법을 사용한다. 누적 합을 계산하여 각 알파벳에 대해 문자열의 시작부터 현재 위치까지 각 알파벳이 몇 번 나타났는지 저장한다. 이렇게 하면 각 쿼리를 빠르게 처리할 수 있다.

코드 설명

1. 문자열 'S' 와 쿼리 수 'Q' 를 입력받는다.
2. 각 알파벳에 대한 누적 합 배열 CumulativeSums를 초기화 한다.
3. 문자열 'S' 를 순회하며 각 문자에 대한 누적 합을 계산한다.
4. 쿼리를 순회하며 각 쿼리에 대해 계산한다.

• 주어진 구간 [start, end] 내에 특정 문자가 몇 번 나타나는지 CumulativeSums를 이용하여 계산

5. 각 쿼리마다 계산한 결과를 출력한다.

Python3으로 제출하니 50점을 맞았지만 pypy3로 제출하니 100점을 맞을 수 있었다.