[백준] 16139 - 인간-컴퓨터 상호작용

1. 문제 요약

문자열 S가 주어지고, 여러 개의 질의가 들어온다.

각 질의는 다음과 같다:

alpha[l][r]

 

👉 구간 [l, r]에서 문자 alpha가 몇 번 등장하는지 구하기

---

2. 처음 접근 (딕셔너리 + 완전탐색)

처음에는 문자별 인덱스를 저장하고, 매 쿼리마다 직접 확인했다.

panels = dict()

for i, c in enumerate(s):
    if c not in panels:
        panels[c] = [i]
    else:
        panels[c].append(i)

for k in panels[alpha]:
    if l <= k <= r:
    	count += 1

 

❌ 문제점

• 질의마다 리스트를 순회 → 최악 O(N)
• 시간초과 발생

---

3. 개선 시도 (누적합 / Prefix Sum)

그래서 각 알파벳별 누적합 배열을 만들었다.

panels = [[0] * (n+1) for _ in range(26)]

for i in range(n):
    for j in range(26):
        panels[j][i+1] = panels[j][i]
        panels[ord(s[i]) - ord('a')][i+1] += 1

 

그리고 질의는:

panels[k][r+1] - panels[k][l]

 

👉 시간복잡도:

• 전처리: O(26N)
• 질의: O(1)

---

그런데도 100점이 안 나옴…

이게 핵심 포인트다.

👉 알고리즘은 맞는데 Python에서 통과 못함

이유 1) 복사 비용

 

for j in range(26):
    panels[j][i+1] = panels[j][i]

 

• 문자 하나마다 26번 복사
• 총 연산량: 약 26 × N

👉 Python에서는 이 "복사"가 생각보다 무겁다

---

이유 2) 메모리 부담

 

26 × (n+1) 크기의 리스트

 

• Python int는 객체라서 메모리 사용량 큼
• 테스트 케이스에 따라 성능 저하 발생

---

⚡ 해결 방법 1 — bisect (정석)

문자 위치만 저장하고, 이진 탐색으로 개수를 구하는 방식

 

from bisect import bisect_left, bisect_right

panels = [[] for _ in range(26)]

for i, ch in enumerate(s):
    panels[ord(ch) - 97].append(i)

    left = bisect_left(arr, l)
    right = bisect_right(arr, r)

    print(right - left)

 

✔ 특징

• 전처리: O(N)
• 질의: O(log N)
• 메모리 효율 좋음

👉 Python에서는 가장 안정적인 정답

---

⚡ 해결 방법 2 — Prefix 최적화 (내가 통과한 방법)

누적합 방식 유지하면서, 입출력 + 연산 최적화 적용

 

import sys

readline = sys.stdin.buffer.readline

s = readline().rstrip()
q = int(readline())
n = len(s)

panels = [[0] * (n + 1) for _ in range(26)]

for i, ch in enumerate(s, 1):
	prev = i - 1
for row in panels:
    row[i] = row[prev]
    panels[ch - 97][i] += 1

out = []

for _ in range(q):
    alpha, l, r = readline().split()
    l = int(l)
    r = int(r) + 1
    k = alpha[0] - 97
    out.append(str(panels[k][r] - panels[k][l]))

    sys.stdout.write("\n".join(out))

---

4. 적용한 최적화 포인트

 1) sys.stdin.buffer.readline

• 입력 속도 개선

 2) print → sys.stdout.write

• 출력 병목 제거

 3) bytes 활용

 

s = readline().rstrip()

 

• ord() 없이 바로 연산 가능

 4) enumerate(..., 1)

• 인덱스 계산 줄이기

---

5. 결론

“알고리즘이 맞다고 해서 Python에서 통과하는 건 아니다”

이 문제에서 배운 것:

• 이론적으로는 prefix sum이 더 빠름 (O(1) 질의)
• 하지만 Python에서는
  • 리스트 복사 비용
  • 메모리 구조
    때문에 느려질 수 있음

방법결과

완전탐색	❌ 시간초과
prefix sum	⚠ 일부 테스트 실패
prefix + 최적화	✅ 통과
bisect	✅ 가장 안정