728x90
반응형
16139번: 인간-컴퓨터 상호작용
첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째
www.acmicpc.net
1. 문제 설명
2. 풀이과정
해당 문제를 처음 풀었을 때는 그저 입력을 받고 문자열에서 해당 범위를 추출해 그 범위에서 문자의 개수를 구하는 방식으로 해결하였다. 해당 방법으로 문제를 해결하니 50점이 나왔다.
하여 어떻게 100점으로 문제를 해결할 수 있을까 고민하던 중 누적 합으로 해결하면 시간이 더 단축될 것 같았다.
a~z를 0~25번 인덱스로 생각하여 한 행이 26칸이 되도록 2차원 리스트를 생성해 주어 문자열의 문자를 하나씩 포함하면서 해당 문자열의 각 문자 개수를 리스트에 추가하도록 구현하였다.
문자열의 끝까지 각 문자의 개수를 리스트에 추가하면 개수를 저장한 2차원 리스트는 각 행 별로 문자열에서 각 위치까지의 문자 개수가 저장되어 있게 된다.
이후 질문을 입력받으며 문자열의 끝 위치의 해당 문자 개수에서 문자열의 시작 위치 이전의 해당 문자 개수를 빼주면 주어진 문자열의 범위에서 해당 문자의 개수를 구할 수 있다.
이때 문자의 개수를 저장한 2차원 리스트가 0개의 문자부터 시작된 것을 고려한다.
- sys.stdin.readline() 함수를 사용하기 위해 sys 패키지를 불러온다. import sys
- 문자열을 입력받는다. S = sys.stdin.readline().rstrip()
- 질문의 개수를 입력받는다. q = int(sys.stdin.readline())
- 각 문자열의 범위만큼 각 문자의 개수를 저장할 2차원 리스트를 생성하고 초기 0번째 행은 모두 0으로 초기화한다. 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)
반응형
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)
728x90
반응형
'백준' 카테고리의 다른 글
[백준] 1992번 : 쿼드트리 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2024.07.05 |
---|---|
[백준] 2630번 : 색종이 만들기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2024.06.24 |
[백준] 13305번 : 주유소 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2024.06.08 |
[백준] 25682번 : 체스판 다시 칠하기 2 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2024.06.02 |
[백준] 2559번 : 수열 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2024.01.13 |
[백준] 12865번 : 평범한 배낭 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2024.01.07 |
[백준] 9251번 : LCS - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.12.29 |
[백준] 2565번 : 전깃줄 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.12.28 |