[백준/파이썬] 16139

https://www.acmicpc.net/problem/16139

인간-컴퓨터 상호작용(광주과학기술원 HOLICS 알고리즘 대회 2018 B번)

💫 알고리즘

누적합 Prefix Sum

배열의 특정 구간 합을 빠르게 계산하기 위한 기법, 미리 누적된 값을 저장하여 활용

누적합 배열을 생성한 후, 구간 합을 O(1) 연산으로 빠르게 조회

쿼리 처리 속도가 매우 빨라짐

---

💡 풀이방향

🐢 누적합을 사용하여 주어진 문자열에서 특정 알파벳이 특정 구간에서 몇 번 등장했는지 빠르게 찾기

1️⃣ 질문은 q개가 주어지며, 매 구간에서의 알파벳 등장 횟수를 계산

2️⃣ 문자열 길이 S ≤ 200,000, 질문 q ≤ 200,000으로 매번 직접 탐색하면 비효율적

3️⃣ 단순하게 S[l:r+1]로 슬라이싱 후 count(a)를 하면 O(N)

→ q번 질문을 처리하면 O(N * q) = 4 * 10^10으로 1초 안에 처리 불가

4️⃣ 각 알파벳('a'~'z')의 등장 횟수를 누적합 배열에 저장하여 빠르게 조회

5️⃣ 문자마다 등장 횟수를 저장하는 누적합 배열 cnt를 활용해 O(1)에 구간 개수를 계산

---

🌟 코드 구현 + 👀 풀이

[전체 코드]

import sys
input = sys.stdin.readline

S = input().rstrip()
q = int(input())

# 누적합 배열 초기화(각 알파벳 별 등장 횟수를 저장하는 2차원 배열)
cnt = [[0] * 26] 

for i in range(len(S)):
    cnt.append(cnt[len(cnt) - 1][:]) # 직전 누적 배열 복사(새로운 누적합 배열 생성)
    cnt[i + 1][ord(S[i]) - 97] += 1 # 현재 문자의 등장 횟수 +1

for _ in range(q):
    a, l, r = input().split()
    result = cnt[int(r) + 1][ord(a) - 97] - cnt[int(l)][ord(a) - 97]
    print(result)

 

cnt.append(cnt[len(cnt) - 1][:])

이전 cnt 배열을 deep copy하여 새로운 배열 추가

이전 상태 그대로 유지하며 등장 횟수 갱신을 위해 사용

🤔 [len(cnt)-1]로 cnt의 마지막 요소를 가져오는 건 알겠는데, [:]로 리스트 슬라이싱은 왜 하나요?

🐢 원본 객체의 주소값을 복사하는 것이 아닌, 참조할 객체 자체를 복사하기 위해서예요!

리스트 슬라이싱의 경우 새로운 리스트의 값을 변경해도 기존 리스트는 변경되지 않지만,

Shallow Copy의 경우 같은 주솟값, 같은 리스트를 공유하기 때문에 값이 함께 변경되기 때문인데요. 밑의 예시 코드를 돌려보시면 이해하실 거예요!!

# Deep Copy
cnt = [[0, 0, 0]]  
cnt.append(cnt[len(cnt) - 1][:]) 
cnt[-1][0] += 1  
print(cnt)
# Shallow Copy
cnt = [[0, 0, 0]]
cnt.append(cnt[len(cnt) - 1])  
cnt[-1][0] += 1  
print(cnt)

 

cnt[i + 1][ord(S[i]) - 97] += 1

현재 문자 S[i]의 해당 알파벳에 해당하는 누적 횟수 증가

ord(S[i]) - 97 → 'a' = 97, 'b' = 98 이므로 'a'는 0, 'b'는 1, 즉 알파벳 당 col 배정

🤔 왜 i + 1부터 시작하는 건가요?

🐢 만약 i = 0부터 바로 갱신을 해버리면 l = 0인 쿼리에서 빼야 할 부분(cnt[0])이 올바른 빈 상태가 아니어서 결과가 잘못 계산되기 때문이죠!

 

result = cnt[int(r) + 1][ord(a) - 97] - cnt[int(l)][ord(a) - 97]

cnt[int(r) + 1]: S[0]부터 S[int(r)]까지의 누적 개수

cnt[int(l)]: S[0]부터 S[int(l) - 1]까지의 누적 개수