[BOJ] #16139번: 인간-컴퓨터 상호작용

 

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

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

 

 

문제

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

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

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

 

입력

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

 

출력

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

 

서브 태스크 1 (50점)

문자열의 길이는 2,000$2,000$자 이하, 질문의 수는 2,000$2,000$개 이하이다.

 

서브 태스크 2 (50점)

추가 제한 조건이 없다.

 

 

문제풀이

문제 풀이 자체는 누적 합의 원리를 활용하면 쉽게 풀 수 있다. 50점-100점 이렇게 점수를 다르게 주는데, 이 또한 원리만 갖게 하고, PYPY3로 제출하면 100점을 얻을 수 있다. 100점을 얻고 싶다면 input() 사용하지 말고, sys.stdin.readline().rstrip() 사용하자.

 

 

----- 50점 -----

 

import sys
s = input()
s_list = list(set(list(s)))
n = int(sys.stdin.readline())

li = [[0]*len(s) for i in range(len(s_list))]
for a in range(0, len(s_list)):
    a_num = 0
    for b in range(0, len(s)):
        if s_list[a] == s[b]:
            a_num += 1
            li[a][b] += a_num
        else:
            li[a][b] += a_num

for i in range(n):
    s, a, b = map(str, input().split())
    if s in s_list:
        s_index = s_list.index(s)
        a = int(a)
        b = int(b)
        if a == 0:
            num = 0
        else:
            num = li[s_index][a-1]
        print(li[s_index][b] - num)
    else:
        print(0)

 

 

----- 100점 -----

 

import sys
s = sys.stdin.readline().rstrip()
s_list = list(set(list(s)))
n = int(sys.stdin.readline())

li = [[0]*len(s) for i in range(len(s_list))]
for a in range(0, len(s_list)):
    a_num = 0
    for b in range(0, len(s)):
        if s_list[a] == s[b]:
            a_num += 1
            li[a][b] += a_num
        else:
            li[a][b] += a_num

for i in range(n):
    s, a, b = map(str, sys.stdin.readline().rstrip().split())
    if s in s_list:
        s_index = s_list.index(s)
        a = int(a)
        b = int(b)
        if a == 0:
            num = 0
        else:
            num = li[s_index][a-1]
        print(li[s_index][b] - num)
    else:
        print(0)