[백준]_16139번 : 인간-컴퓨터 상호작용(파이썬)

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

 

누적합과 사전을 적절히 사용하면 무난하게 풀렸던 문제이다. 문제에 나와 있듯이 문자열의 길이와 질문의 수는 최대 200,000까지 늘어날 수 있기 때문에 질문을 하나 받을 때마다 문자열 구간 [l, r]에서 목표 알파벳이 몇 개 나오는지 다시 샐 여유가 없다. 따라서 아래와 같은 접근을 사용하여 시간을 줄이는 전략을 선택했다.

 

접근

 

알파벳을 target, l을 start, r을 finish라고 하자. 또한 과거에 질문받은 알파벳에 대한 리스트를 저장하기 위해서 사전 repo도 선언해 주자.

1. 만약 target이 repo에 존재한다면 리스트인 repo [target]을 갖고 와서 사용해 준다. 
2. repo에 target이 없다면(처음으로 질문된 알파벳이라면) 0으로 초기화되어 있고 길이가 문자열 S와 같은 리스트를 선언해 준다.  
3. 이제 문자열 S의 알파벳을 하나씩 target과 비교해 가며 target과 일치하면 새로운 리스트에 +1을 해주며 누적합 리스트를 만들어 준다. 
4. start와 finish를 이용해 답을 내고 사용한 누적합 리스트는 repo에 추가해 준다.

최종 코드 >>

import sys

input = sys.stdin.readline

userinput = input().strip()
cnt = int(input())

repo = {}

for _ in range(cnt):
    target, start, finish = input().split()
    start = int(start)
    finish = int(finish)
    if target in repo: # repo에 target이 있다면
    	# start가 0이면 예외적으로 repo[target][finish]만 답이 된다.
        print(repo[target][finish] - repo[target][start - 1] if start > 0 else repo[target][finish])
    else:
        ls = [0] * len(userinput)
        add = 0
        for i in range(len(userinput)):
            if target == userinput[i]:
                add += 1
                ls[i] = add
            else:
                ls[i] = ls[i - 1]
        print(ls[finish] - ls[start - 1] if start > 0 else ls[finish])
        repo[target] = ls

 

살짝 이해가 안 갈 수 있는 부분은 다음 부분이다.

else:
    ls[i] = ls[i - 1]

 

만약 i가 0이면 예외 처리를 해줘야 하는 것이 아닌가 생각이 들 수도 있다. 하지만 상관이 없다.

 

왜냐하면 ls는 앞부분부터 채워지기 때문에 i가 0일 때  ls [i-1]은 반드시 0이다. 따라서 코드 문맥상 S의 첫 번째 알파벳이 target과 다를 때  ls [0]=ls [-1]이 되는 것이고 ls [-1]은 반드시 0이기 때문에(물론 반복문의 끝을 향해 가면 0이 아닐 수도 있지만 그때쯤이면 ls [-1]에 접근할 일이 아예 없다.) ls [0]=0이 된다.

 

만약 S가 "a"이고 target이 'b'이면 어떻게 될까?

 

S의 길이가 1이기 때문에 start와 finish는 반드시 0이다. 즉 ls [0]과 ls [-1]이 같은 상황이므로 그냥 0에 0을 대입하는 해프닝으로 끝나게 된다.