[백준] 16139 인간 (Python 파이썬)

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

16139번: 인간-컴퓨터 상호작용

문제 설명

특정 문자열 S, 특정 알파벳 α와 문자열의 구간 [l,r]이 주어지면

S의 l번째 문자부터 r번째 문자 사이에 α가 몇 번 나타나는지 구하는 프로그램을 작성하자.

문자열의 문자는 0번째부터 세며, l번째와 r번째 문자를 포함해서 생각한다.

---

풀이 과정

이 문제는 누적 합 으로 풀어야 시간초과 없이 해결할 수 있다.

 

만약, 매번 l부터 r까지 모든 문자를 돌며 개수를 카운트하는식으로 하여

N번 계산한다면 시간초과 오류가 발생하기 때문에

누적합을 이용해야 한다.

즉, 누적해서 횟수를 쌓아가야 한다는 뜻이다.

 

예를 들어 kakaotistory 라는 문자열이 있고, k가 들어가는 횟수를 센다고 할때,

k가 등장하지 않는 인덱스에는

k[5] = k[4]

k[6] = k[5] 

...

처럼 그 전 인덱스의 횟수를 그대로 쌓아가고

k 문자가 나타날 때는 그 인덱스에 +1을 추가해주어 누적해서 쌓아가면 된다.

 

kakaotistory 같은 경우 k가 0번째와 2번째에 나타나기 때문에k[0] = 1, k[1] = 1, k[2] = 2 ... k[11] = 2 이런식으로 쌓아가면 된다.

 

이렇게 알파벳마다 누적합 횟수를 저장해놓으면,

0번째부터 6번째 문자 사이에 k가 몇개 들어있는지 알아보아야 할 때,

매번 카운트 할 필요 없이

k[6] - k[0] 의 값을 구해서 바로 횟수를 구할 수 있기 때문이다.

 

그래서, 가장 먼저 문자열을 입력받고 나서

a~z별로 누적합을 먼저 저장해놓고

매 질문이 들어올때는 저장해놓은 누적합의 계산을 통해서 바로 답을 구하면 된다.

 

이를 파이썬으로 구현한 코드는 다음과 같다.

import sys

input = sys.stdin.readline
s = list(input().rstrip())
n = int(input().rstrip())

cList = [[0] * len(s) for _ in range(26)]

for i in range(len(s)):
  cList[ord(s[i])-ord('a')][i] += 1

for i in range(26):
  for j in range(1, len(s)):
    cList[i][j] += cList[i][j-1]

for i in range(n):
  a, l, r = input().split()
  tmp = cList[ord(a)-ord('a')][int(r)] - cList[ord(a)-ord('a')][int(l)]

  if s[int(l)] == a:
    tmp+=1
    
  print(tmp)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !