[Java+Python]16139번, 인간-컴퓨터 상호작용

목차

 

누적 합

 

[Java+Python]11659번, 구간 합 구하기 4

[Java+Python]2559번, 수열

[Java+Python]10986번, 나머지 합

[Java+Python]11660번, 구간 합 구하기 5

[Java+Python]25682번, 체스판 다시 칠하기 2

 

문제

 

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

'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 

자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'

승재를 도와 특정 문자열 $S$, 특정 알파벳 $\alpha$와 문자열의 구간 $[l, r]$이 주어지면 

$S$의 $l$번째 문자부터 $r$번째 문자 사이에 $\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 

 

승재는 문자열의 문자는 $0$번째부터 세며, $l$번째와 $r$번째 문자를 포함해서 생각한다. 

 

주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 $q$번 할 것이다.

 

입력

 

첫 줄에 문자열 $S$가 주어진다. 

 

문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 

 

두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 

 

세 번째 줄부터 $(q+2)$번째 줄에는 질문이 주어진다. 

 

각 질문은 알파벳 소문자 $\alpha_i$와 $0\leq l_i\leq r_i<|S|$를 만족하는 정수 $l_i, r_i$가 공백으로 구분되어 주어진다.

 

출력

 

각 질문마다 줄을 구분해 순서대로 답변한다. 

$i$번째 줄에 $S$의 $l_i$번째 문자부터 $r_i$번째 문자 사이에 $\alpha_i$가 나타나는 횟수를 출력한다.

 

풀이

 

제목은 다소 거창하지만 결국 문자열 $S$의 $l_i$번째 문자부터 $r_i$번째 문자 사이에 $\alpha_i$가

 

몇 번 나타나는지 누적 합으로 계산하는 문제이다.

 

문제를 풀이하는 알고리즘을 간결하게 정리하면 아래와 같다.

 

1. 입력으로 주어진 문자열을 str에 입력받고 질문 개수 q를 입력받는다. 여기서 str의 길이를 n이라 한다.
2. 누적합을 저장할 (26) x (n + 1) 크기의 이중 배열 sum을 선언하고 이중 반복문을 돌며 값을 채운다.
   
   1. 여기서 sum[i][j]의 값은 문자 j가 문자열 str의 1부터 i까지의 부분 문자열에서 출현한 횟수이다.
   2. str.charAt(i) - 'a'는 해당 위치의 문자에 대응하는 알파벳의 인덱스이다.
3. 해당 배열을 바탕으로 주어진 질문에 대해 특정 문자의 출현 횟수를 계산한다.
   1. 입력을 특정 문자에 해당하는 인덱스 chr, 시작 위치 start, 끝 위치 end로 변환한다.
   2. sum[chr][end + 1] - sum[chr][start]를 이용해 출현 횟수를 계산한다.
4. 출력한다.

 

시간복잡도 최적화를 위해서 자바에서는 StringBuilder를, 파이썬에서는 sys.stdout.write()를 사용했다.

 

하지만 이렇게까지 줄였는데도 파이썬 3에서는 50점밖에 받지 못해서 PyPy3으로 제출할 수밖에 없었다..

 

Java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Prob16139_4 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		String str = br.readLine();
		int n = str.length();
		int q = Integer.parseInt(br.readLine());
		int[][] sum = new int[26][n + 1];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 26; j++) { // 문자열 처음 인덱스부터 순회
				sum[j][i + 1] = sum[j][i];
			}
			sum[str.charAt(i) - 'a'][i + 1]++; // 알파벳 -> 아스키코드 매핑
		}

		for (int i = 0; i < q; i++) {
			String[] query = br.readLine().split(" ");
			int chr = query[0].charAt(0) - 'a';
			int start = Integer.parseInt(query[1]);
			int end = Integer.parseInt(query[2]);

			int count = sum[chr][end + 1] - sum[chr][start];
			sb.append(count).append('\n');
		}

		System.out.println(sb);
	}
}

 

Python

 

import sys

string = sys.stdin.readline().rstrip()
n = len(string)
q = int(sys.stdin.readline().rstrip())
lst = [[0] * (n + 1) for _ in range(26)]

for i, char in enumerate(string):
    for j in range(26):
        lst[j][i + 1] = lst[j][i]
    lst[ord(char) - ord('a')][i + 1] += 1

results = []

for _ in range(q):
    query = list(sys.stdin.readline().rstrip().split())
    char = ord(query[0]) - ord('a')
    start = int(query[1])
    end = int(query[2])

    count = lst[char][end + 1] - lst[char][start]

    results.append(count)

sys.stdout.write('\n'.join(map(str, results)) + '\n')

 

Performance