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

구간합 문제이다.

문제 유형이 뭔지 알았음에도 이번 문제에 구간합을 어떻게 적용해야할지 감이 안잡혀서 일단 단순하게 풀었다.

import sys
S = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline().rstrip())
question = []
for _ in range(q):
    alpha, l, r = sys.stdin.readline().rstrip().split()
    temp = S[int(l) : int(r) + 1]
    count = 0
    for t in temp:
        if t == alpha:
            count += 1
    print(count)

단순하게 문자열에서 l~r 구간의 문자열을 슬라이싱 해서 알파벳 갯수를 count 했다.

이중for문이니까 역시 시간 초과될 것 같았고, 50점 맞았다 ㅠㅠ.

그래서 블로그 검색해서 사람들이 구간합을 어떻게 적용하는지 참고했다.

---

문자열의 각 인덱스에서의 a ~ z의 갯수를 list로 관리하는 방식을 사용 > 2차원 배열

i 번째 문자시점의 알파벳 갯수 누적 합 : count[i]

 

- 크기 26의 list 에 문자열 S 의 i 번째 문자 까지 알파벳 소문자 26개의 출현 갯수를 저장한다.

예를 들어 "hiyoumini" 라는 문자열의 7번째 문자에서의 (시작 인덱스 = 1) 각 알파벳 별 누적 갯수는 위와 같고, List로 저장했다.

 

그러면 문자열 S의 4 - 7 구간에서의 문자 'i'의 갯수는

count[7][ord('i') - 97] - count[3][ord('i') - 97] =  2 - 1 = 1 이 된다.

 

* 알파벳 소문자의 아스키코드에서 -97을 하면 문자 'a' - 'z'를 0 ~ 25의 인덱스로 관리할 수 있다.

import sys
from copy import deepcopy
s = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline().rstrip())
count = [[0] * 26]
for i, ch in enumerate(s):
    count.append(deepcopy(count[len(count) - 1]))
    count[i + 1][ord(ch) - 97] += 1

for _ in range(q):
    alpha, l, r = sys.stdin.readline().rstrip().split()
    answer = count[int(r) + 1][ord(alpha) - 97] - count[int(l)][ord(alpha) - 97]
    print(answer)

하지만 여전히 50점 ㅠㅠ 🥹

i 번째 문자열까지의 알파벳 갯수에 접근하는데 (count[i]) 시간이 오래 걸리나 싶어서 list인 count를 dictionary 타입으로 변경해봤다.

import sys
from copy import deepcopy
s = sys.stdin.readline().rstrip()
count = {0 : [0] * 26}

q = int(sys.stdin.readline().rstrip())
for i, ch in enumerate(s):
    count[i + 1] = deepcopy(count[len(count) - 1])
    count[i + 1][ord(ch) - 97] += 1

for _ in range(q):
    alpha, l, r = sys.stdin.readline().rstrip().split()
    answer = count[int(r) + 1][ord(alpha) - 97] - count[int(l)][ord(alpha) - 97]
    print(answer)

쒹... 그래도 50점

다른 사람들 블로그도 참고해보다가... deepcopy가 문제인가 싶어서 deepcopy 시간 복잡도 관련 포스팅 참고한 뒤, deepcopy 보단 slicing으로 리스트를 복사하는게 더 낫대서 변경했다!

 

deepcopy(count[len(count) - 1]  -> count[len(count) - 1][:] 

---

최종 소스

import sys

s = sys.stdin.readline().rstrip()
count = {0 : [0] * 26}

q = int(sys.stdin.readline().rstrip())
for i, ch in enumerate(s):
    count[i + 1] = count[len(count) - 1][:]
    count[i + 1][ord(ch) - 97] += 1

for _ in range(q):
    alpha, l, r = sys.stdin.readline().rstrip().split()
    answer = count[int(r) + 1][ord(alpha) - 97] - count[int(l)][ord(alpha) - 97]
    print(answer)

드디어 100점!

dictionary가 아니고 list도 100점 나오는지 확인해보는게 좋을 것 같아서 확인했다.

결론 : count 변수가 list인지 dictionary 인지는 점수에 영향을 미치지 않는다.

import sys

s = sys.stdin.readline().rstrip()
count = [[0] * 26]
# count = {0 : [0] * 26}

q = int(sys.stdin.readline().rstrip())
for i, ch in enumerate(s):
    count.append(count[len(count) - 1][:])
    # count[i + 1] = count[len(count) - 1][:]
    count[i + 1][ord(ch) - 97] += 1

for _ in range(q):
    alpha, l, r = sys.stdin.readline().rstrip().split()
    answer = count[int(r) + 1][ord(alpha) - 97] - count[int(l)][ord(alpha) - 97]
    print(answer)

 

우당탕탕... PyPy3으로도 해보고 해봤습니다만 PyPy3으로 바꾸는건 여기서 안먹혔다 ㅎ 히히

아 최종소스에서 list 변수를 쓰는게 메모리를 덜 사용하고 시간도 0.1초 정도 짧았다.