[BAEKJOON] 16139 인간-컴퓨터 상호작용

문제 요약

• 알고리즘 분류: 구간합, 누적합, 수학
• 난이도: Silver1
• 문제내용:
  • 문자열 S가 주어지고 각 테스트케이스 마다  문자와 인덱스 시작점과 끝을 준다.
  • 문자열에서 시작점과 끝사이에 문자 몇개 있는지 출력해라
• 사이트 : https://www.acmicpc.net/problem/16139

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

문제풀이

 

 이번문제는 두가지 경우가 있는데 50점짜리는 각 시작점 부터해서 끝지점까지 탐색해서 해당되는 문자 몇개인지 출력을 하면되기 때문에 쉽다. 하지만 100점은 테스트 케이스가 많아서 시간을 최대한 단축을 시키는 방법으로 가야한다. 그래서 사용할수 있는 방법이 누적합 방법이다. 누적합에 대한 설명은 아래의 사이트에 참조하면된다.

https://jih3508.tistory.com/50

[알고리즘 이론] 구간합, 누적합(prefix sum)

누적합을 어떻게 문제를 적용 할 예정이라면 2차원 배열로 열은 각 알파펫을 나타내고 행은 문자열 위치를 나타 낼것이다. 

위 예제를 표로 나타낸것이다. 하지만 코드 상에서는 위 그림대로 나오지 않을것이고 a ~ z를 표로 나타낸 다음에 할것이다.  그냥 간단하게 참고용으로 보면된다.

 위 표를 보면 e기준으로 봤을떼 첫번째 인덱스에서 1이 추가가 되었고 7번째 인덱스에서느 2가 늘어난것을 볼 수가 있다.

처음 인덱스는 문자열 첫번째 알파벳만 1만 되어있고 나머지는 0으로 시작하고 첫번째 인덱스 부터는 앞에 열의 값을 추가하고 해당되는 알파벳만 +1만 하면된다.

그 다음 문자열 탐색이 끝나면 각 케이스마다 알파벳과 탐색범위 끝지점에 +1 위치의 값과 시작한 위치의 값만 해주면 끝이다.

1.  a ~ z 까지 열과 문자열 길이만큼 행을 2차원 배열로 선언한다.
2. 문자열 탐색하면 각 알파벳에 이전 행의 값을 추가하고 탐색한 문자열 위치의 알파벳만 +1한다.
3. 각 케이스 마다 알파벳의 끝지점 +1의 위치의 값과 시작점 위치 값을 뺀다.

Code

Python

python으로 돌렸을때는 시간 초과가 나온다. pypy로 돌려야 통과가 된다.

from collections import Counter
import sys

input = sys.stdin.readline
print = sys.stdout.write

S = input()
n = len(S)
dic = {char : [0] * (n + 1) for char in Counter(S).keys()}
dic[S[0]][1] = 1
for i in range(1, n):
    for key in dic.keys():
        dic[key][i + 1] = dic[key][i] + int(S[i] == key)


for _ in range(int(input())):
    char, start, end = input().split()
    start, end = int(start), int(end)
    result = 0
    if char in dic.keys():
        result = dic[char][end + 1] - dic[char][start]
    print("%d\n"%(result))

 Java

java 주의점은 각 케이스마다 출력함수를 쓰지 말고 StringBuilder 클래스를 사용해서 각 케이스 답을 저장한다음 맨 마지막에 출력하면 통과가 된다.

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String S = br.readLine();
		int n = S.length();
		int[][] dic = new int[26][n+1];
		int ord = 'a';
		dic[S.charAt(0) - ord][1] = 1;
		for(int i = 1; i < n; i++) {
			for(int j = 0; j < 26; j++) {
				dic[j][i + 1] = dic[j][i] + (S.charAt(i) == j + 'a'? 1: 0);
			}
		}
		
		StringTokenizer st;
		char ch;
		int start, end;
		
		n = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			
			ch = st.nextToken().charAt(0);
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			sb.append(dic[ch - 'a'][end + 1] - dic[ch - 'a'][start] + "\n");
		}
		System.out.println(sb);
	
	}
			
}