[백준] 16139번 : 인간-컴퓨터 상호작용 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

2. 풀이과정

해당 문제를 처음 풀었을 때는 그저 입력을 받고 문자열에서 해당 범위를 추출해 그 범위에서 문자의 개수를 구하는 방식으로 해결하였다. 해당 방법으로 문제를 해결하니 50점이 나왔다.

하여 어떻게 100점으로 문제를 해결할 수 있을까 고민하던 중 누적 합으로 해결하면 시간이 더 단축될 것 같았다.

a~z를 0~25번 인덱스로 생각하여 한 행이 26칸이 되도록 2차원 리스트를 생성해 주어 문자열의 문자를 하나씩 포함하면서 해당 문자열의 각 문자 개수를 리스트에 추가하도록 구현하였다.

문자열의 끝까지 각 문자의 개수를 리스트에 추가하면 개수를 저장한 2차원 리스트는 각 행 별로 문자열에서 각 위치까지의 문자 개수가 저장되어 있게 된다.

이후 질문을 입력받으며 문자열의 끝 위치의 해당 문자 개수에서 문자열의 시작 위치 이전의 해당 문자 개수를 빼주면 주어진 문자열의 범위에서 해당 문자의 개수를 구할 수 있다.

이때 문자의 개수를 저장한 2차원 리스트가 0개의 문자부터 시작된 것을 고려한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 패키지를 불러온다. import sys
2. 문자열을 입력받는다. S = sys.stdin.readline().rstrip()
3. 질문의 개수를 입력받는다. q = int(sys.stdin.readline())
4. 각 문자열의 범위만큼 각 문자의 개수를 저장할 2차원 리스트를 생성하고 초기 0번째 행은 모두 0으로 초기화한다. count = [[0] * 26]
5. 문자열의 길이만큼 반복하며 for i in range(len(S))
6. 바로 이전 문자열의 각 문자 개수 결과를 동일하게 추가하고 count.append(count[len(count) - 1][:]
7. 새롭게 늘어난 범위의 문자의 개수를 더해준다. count[i + 1][ord(S[i]) - 97] += 1
8. 질문의 개수만큼 반복하며 for _ in range(q)
9. 문자, 시작 위치, 끝 위치를 입력받는다. a, l, r = map(str, sys.stdin.readline().split())
10. 주어진 시작 위치부터 끝 위치까지의 범위에서 해당 문자의 개수를 구한다. result = count[int(r) + 1][ord(a) - 97] - count[int(l)][ord(a) - 97]
11. 주어진 범위에서 구한 문자의 개수를 출력한다. print(result)

반응형

3. 소스코드

import sys

S = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline())

count = [[0] * 26]
for i in range(len(S)):
    count.append(count[len(count) - 1][:])
    count[i + 1][ord(S[i]) - 97] += 1

for _ in range(q):
    a, l, r = map(str, sys.stdin.readline().split())
    result = count[int(r) + 1][ord(a) - 97] - count[int(l)][ord(a) - 97]
    print(result)