알고리즘 유형 : 누적합
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/16139
소스 코드(파이썬)
import sys
input = sys.stdin.readline
S = input().strip()
q = int(input())
pre_len = [[0]*26]
pre_len[0][ord(S[0])-97] = 1
# pre_len는 S에 대해, row자리까지의 부분 문자열에서
# column_alphabet이 몇 개 들어있는지를 value로 갖는
# 2차원 리스트이다.
# 이 때, alphabet에 대해, ord(alphabet)-97은 0~25의 수를 갖고
# 이 것을 pre_len의 column으로 삼아서 알파벳을 인덱싱하게 했다.
# 행과 열을 이 것과 반대로 설정하면, 알파벳별로 len(S)만큼 for를 돌면서
# 총 26개의 부분합을 만듦으로 O(26*len(S))가 소요되는데, 위에서 설명한
# 방법대로 설정하면 O(len(S))만으로 pre_len을 완성할 수 있다.
for idx in range(1, len(S)):
pre_len.append(pre_len[-1][:])
pre_len[idx][ord(S[idx])-97] += 1
for _ in range(q):
alpha, l, r = input().split()
l, r = map(int, [l, r])
alpha_idx = ord(alpha) - 97
if l == 0:
print(pre_len[r][alpha_idx])
else:
print(pre_len[r][alpha_idx] - pre_len[l-1][alpha_idx])
풀이 요약
-
이 문제는 2차원 리스트의 행과 열을 무엇으로 설정하는지가 핵심이다. 그 것에 따라 시간복잡도 차이가 크다.
우선 50점을 받는 풀이의 행 열 설정을 먼저 알아보자.pre_len의 행은 "알파벳", 열은 "S에 대해, column까지의 부분 문자열"을 의미한다. 이 때, 리스트의 value는 "S의 column까지의 부분 문자열에서 행(알파벳)이 들어있는 개수"를 의미한다.
이를 쭉 채워줄때는 이중 for문을 돌게 된다.
26개의 알파벳 각각에 대해, len(S)번 for를 돌면서 누적합을 채워주게 된다.
O(26*len(S))가 소요된다.
이제 100점짜리 풀이의 행 열 설정을 알아보자.pre_len의 행은 "S에 대해, column까지의 부분 문자열"을 의미하고, 열은 "알파벳"을 의미한다. 이 때, 리스트의 value는 "S의 row까지의 부분 문자열에서 열(알파벳)이 들어있는 개수"를 의미한다. 50점 풀이의 행 열 설정을 거꾸로 한 것과 같다.
이렇게 해주면 단일 for문으로 리스트를 모두 채울 수 있다.
일단 pre_len에는 S의 0번째 인덱스까지의 부분 문자열에서 모든 알파벳들의 포함 개수를 원소로 넣어둔다.
그 다음 1부터 len(S)-1까지 돌면서, 다음 구문을 반복한다.
1) pre_len의 마지막 원소(바로 직전 row까지의 모든 알파벳 포함 개수 1차원 리스트)를 복사해서 pre_len에 추가한다.
2) 현재 for의 idx에 해당하는 알파벳에 대해, 아까 추가한 1차원 리스트의 idx번째 원소에 1을 더해준다.
좀 더 요약해보면,
S의 0번째 문자열까지에 대한 정보 리스트를 복사해서 추가하고, 그 리스트는 곧 1번째 문자열까지에 대한 정보를 의미하게 될 것이므로, S의 1번째 문자열에 해당하는 열에 +1을 해준다. 이 것을 끝까지 반복해준다.
-
그 뒤에는 누적합을 이용하여 답을 구해주면 된다.
단, 시작 인덱스가 0인 경우에는, 그냥 r번째까지의 부분 문자열에 대한 값을 바로 출력해주면 된다.
- 참고로, "a"의 10진수 값은 97이다. 즉, ord("a")-97은 0이다. 이런 식으로, a~z를 0~25로 변환하여 리스트의 인덱싱으로 활용할 수 있다.
배운 점, 어려웠던 점
-
행, 열의 설정에 따라 시간복잡도가 유의미하게 차이나는 꽤나 어려운 문제였다... 시간복잡도를 줄여보려고 온갖 방법을 다 써봤는데 모르겠어서 결국 다른 사람 풀이보고 알아냈다.
시간복잡도를 줄일만한 곳이 2차원 리스트 채우는 구문밖에는 없다고는 생각했는데, 행/열 기준을 거꾸로 바꿔볼 생각은 못했다. 참신하고 유익한 문제였다.
