BOJ [Silver I] 인간-컴퓨터 상호작용 - 16139

문제 링크

분류

누적 합(prefix_sum)

문제 설명

승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다.

'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'

승재를 도와 특정 문자열 S, 특정 알파벳 α와 문자열의 구간 [l,r]이 주어지면 S의 l번째 문자부터 r번째 문자 사이에 α가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 0번째부터 세며, l번째와 r번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 q번 할 것이다.

입력

첫 줄에 문자열 S가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 q가 주어지며, 문제의 수는 1≤q≤200,000을 만족한다. 세 번째 줄부터 (q+2)번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 αi와 0≤li≤ri<|S|를 만족하는 정수 li,ri가 공백으로 구분되어 주어진다.

출력

각 질문마다 줄을 구분해 순서대로 답변한다. i번째 줄에 S의 li번째 문자부터 ri번째 문자 사이에 αi가 나타나는 횟수를 출력한다.

아이디어

• 서브태스크가 있는 걸 봐서 & 알고리즘 단계가 누적 합이어서 .. 분명 단순 카운트가 아닐 걸 알았지만 우선 단순 카운트로 한 번 풀었음

• 누적 합인 걸 봐서 알파벳 별로 구간마다 개수를 갱신해주는 거라고 생각은 했는데, 알파벳 개수 x 문자열 길이만큼 세는 것도 시간이 오래 걸리지 않나? 하는 의심과 .. 무엇보다 내 고질병인 냅다 포기하기ㅠ 병이 또 도져서 다른 사람 코드 구경했음 ....

• 잊을 만할 때 다시 풀 거다 ㅜ 흥

내 코드 1: 부분 성공(50점)

import sys
input = sys.stdin.readline

s = input().rstrip()
q = int(input())

for _ in range(q):
    p = input().split()
    sub = s[int(p[1]) : int(p[2])+1]
    print(sub.count(p[0]))

• 주어진 구간만큼으로 부분 문자열 만들고 count() 함수 써서 알파벳의 개수 세주었음

코드 2: 성공(100점) - 누적 합

import sys
input = sys.stdin.readline

s = input().rstrip()
q = int(input())

count = [[0] * 26 for _ in range(len(s))]  # 구간 별로 각 알파벳 개수 셀 배열
count[0][ord(s[0]) - 97] = 1
for i in range(1, len(s)):
    count[i][ord(s[i]) - 97] = 1  # 문자열 (i, i번째 알파벳) 위치 1로 초기화
    for j in range(26):
        count[i][j] += count[i-1][j]  # 직전까지의 알파벳 개수 반영해주기

for _ in range(q):
    a, l, r = input().split()
    l, r = map(int, [l, r])
    if l > 0:
        print(count[r][ord(a) - 97] - count[l-1][ord(a) - 97])
    else:
        print(count[r][ord(a) - 97])

• Python3로 제출하면 또 50점 나오고, Pypy3로 제출해야 100점 나온다

  메모리도 시간도 PyPy가 더 크게 잡히는데 왜,,인지 잘 모르겠다 ㅜ ㅜ

• count는 s의 길이만큼의 행을 가지고, 각 행(i)의 열은 i번째까지 등장하는 알파벳 a~z 각각의 개수를 의미함

  즉, s의 길이 x 알파벳 개수(26) 사이즈의 배열

• 누적 합에 걸맞게, i번째 행에서 알파벳 α의 값(누적 개수)은 i-1번째 행까지의 알파벳 α의 값 + 0 or 1 이 됨

  s[i]가 α이면 +1, 아니면 +0인 것!

• 인덱스 i-1를 사용하므로 i==0 일 때의 배열 값은 count[0][ord(s[0]) - 97] = 1으로 따로 초기화하고, i는 1부터 시작하도록 함

• count 배열 완성하고 나서, q개의 문제에 대해서는

  l이 0이면 그냥 r까지의 총 개수를 의미하므로 count[r][ord(a) - 97]를 프린트 해주고

  l이 0이 아니면 count[r][ord(a) - 97] - count[l-1][ord(a) - 97]을 해주는데, l-1인 이유는 문제에서 l번째, r번째 모두 포함할 것을 요구하기 때문!

• 아스키 코드 변환할 때 ord() 쓰는 거 잊을 뻔했는데 이 문제에서 다시 한 번 상기시켜줌 ㅎㅎ..