BOJ 16139 인간-컴퓨터 상호작용

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

 

 

진짜로 푸는데 개오랜 시간이 걸렸다.. 

일반적인 누적합 문제와 다른 점은 문자별로 다른 누적합 리스트를 가지고 있어야 한다는 것이다.

예를들어 그냥 단순 특정구간 덧셈 계산을 했을때는 일정구간 자연수에 대한 누적합 리스트가필요했지만

이건 문자 별로 필요한 문제이다. 이문제가 골치아팠다. 그럼 리스트 26개를 만들어야되는데, 동적으로 리스트명을 만들어 안에 append시킬 수 있을까? 라는 생각을 했다. 그런데 동적 변수 할당은 있어도 동적으로 리스트를 만드는 것은 존재하지 않았다.

이중리스트를 만들어 인덱스로 접근하는 발상을 생각해내는데 오랜 시간이 걸렸다..

 

일단 for 문으로 26개의 0을 원소로하는 리스트를 요소로 가지는 이중 리스트를 선언한다.

  S = input()
  q = int(input())

  cnt = 0
  ls1 = []
  tmp = []
  result = 0

  for i in range(26):
    ls1.append([0])

그리고 이 리스트의 인덱스를 지표로 삼아 누적합을 구한다. 

i는 0~25 j는 현재 있는 스트링의 문자로써

만약 문자가 현재 순회하고 있는 문자. 그러니까 i가 0 이라면 chr(97+i) "a" 가 현제 인덱스까지 몇개 있었는지 저장한다.

  for i in range(26):
    for j in S:
      if j == chr(97+i):
        cnt += 1
      ls1[i].append(cnt)
    cnt = 0

이후 이 배열을 가지고 주어진 인풋값에 대해 누적합을 구해주는 연산을 해준다.

예를들어

입력 값으로 a 6 10 가 주어졌다고 해보자.

문자로 a가 주어졌으면 ord(tmp[0]) - 97 0이 된다. 

즉 a의 누적합 10 까지의 결과. ls1[0][11] , 에서 6-1까지의 결과 ls1[0][5]를 빼주게 된다.

여기서 더미데이터 0을 넣어준 이유를 알 수 있는데

0이 업성ㅆ다면 result = ls1[ord(tmp[0])-97][int(tmp[2])] -ls1[ord(tmp[0])-97][int(tmp[1])-1]이 되게 된다.

근데 만약에 a 0 2 의 데이터가 주어졌다고 한다면 ls1[0][2] - ls1[0][-1] 이 된다. 그럼 엉뚱한 값이 나옴.

 

 

  for i in range(q):
    tmp = input().split()
    result = ls1[ord(tmp[0])-97][int(tmp[2])+1] -ls1[ord(tmp[0])-97][int(tmp[1])]

    print(result)

 

 

답

from sys import stdin

def main():
  def input():
    return stdin.readline().rstrip()
    
  S = input()
  q = int(input())

  cnt = 0
  ls1 = []
  tmp = []
  result = 0

  for i in range(26):
    ls1.append([0])
  

  
  
  for i in range(26):
    for j in S:
      if j == chr(97+i):
        cnt += 1
      ls1[i].append(cnt)
    cnt = 0

        

  for i in range(q):
    tmp = input().split()
    result = ls1[ord(tmp[0])-97][int(tmp[2])+1] -ls1[ord(tmp[0])-97][int(tmp[1])]

    print(result)

    
  
if __name__ == "__main__":
  main()