구간합 문제라는 걸 몰랐으면 못 풀었을 문제..
풀이
- 문자열 S의 각 원소를 돌면서 해당 알파벳에 해당하는 인덱스를 count해준다.
그러기 위해서 행은 S의 길이, 열은 알파벳수(26개) 크기의 2차원 배열을 만들어준다. (cnt = [[0] * 26 for in range(len(S))]_) - 비효율적으로 이미 계산했던 부분을 다시 계산하지 않기 위해서 앞에까지 계산해서 저장한 부분을 이용한다. (이중 for문)
주의할 점
- S = input().strip()에서 strip을 안 하면 개행문자까지 포함되어 range 오류가 발생한다.
- l이 0이면 cnt[l-1]에서 오류가 발생하기 때문에(사실 빼줄 게 없다.) 다르게 출력한다.
50점
import sys
input = sys.stdin.readline
S = input().strip()
q = int(input())
cnt = [[0] * 26 for _ in range(len(S))]
cnt[0][ord(S[0])-97] = 1
for i in range(1, len(S)):
cnt[i][ord(S[i])-97] = 1
for j in range(26):
cnt[i][j] += cnt[i-1][j]
for _ in range(q):
lst = input().split()
a, l, r = lst[0], int(lst[1]), int(lst[2])
if l == 0:
print(cnt[r][ord(a)-97])
else:
print(cnt[r][ord(a)-97]-cnt[l-1][ord(a)-97])- a, l, r을 다르게 지정하는 코드도 있던데 나는 알아보기 쉽게 저렇게 지정해주었다.
- 하지만 50점... 왜인지 모르겠어서 구글링을 했다.
원인은 구간합을 구하는 부분을 비효율?적으로 해서 그런 것 같다.
해당 부분을 for문을 한 번 더 돌아서 다 더해주기보다는, 슬라이싱을 이용해서 리스트 복사본을 이용하니까 100점이 나온다.
100점
import sys
input = sys.stdin.readline
S = input().strip()
q = int(input())
cnt = [[0] * 26]
cnt[0][ord(S[0])-97] = 1
for i in range(1, len(S)):
cnt.append(cnt[i-1][:])
cnt[i][ord(S[i])-97] += 1
for _ in range(q):
lst = input().split()
a, l, r = lst[0], int(lst[1]), int(lst[2])
if l == 0:
print(cnt[r][ord(a)-97])
else:
print(cnt[r][ord(a)-97]-cnt[l-1][ord(a)-97])- 그냥 append해주기 위해 cnt는 2차원 리스트로 만들되, 행은 1로 만들어 주었다.
- 몇몇 분들의 코드처럼 enumerate로 만들어서 할까 했는데, 그럼 뒤에 코드에 +1씩 해주어야 돼서 더 별론 것 같아 관두었다. (예를 들면, r대신 r+1)
결과
