백준 16139번 풀이

16139번 링크

어제 푸념한걸 기반으로 풀이했다. 각 알파벳의 누적합을 따로따로 구하는 식으로 풀었다. 처음에는 sum[rt]-sum[lt]의 형태로 풀다가 생각해보니 나는 부분합 알고리즘이 아닌 누적합을 배운건데 왜 저렇게 하고 있지? 하는 생각이 들었고,

sum = s[rt-1] + a[i] -s[lt];

이렇게 해서 풀었다!! 시간제한도 안걸렸고 무사히 통과했다. 최근에 푼 알고리즘 문제중에서 가장 보람찼다.

코드는 아래와 같다. 지저분해서 리팩토링을 할까? 했지만 음... 다음 문제를 더 깔끔하게 풀어보자 라는 태만에 가득찬 생각을 하며 접었다.

package cumulativesum;

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

public class No16139Forth {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		char[] input = br.readLine().toCharArray();
		int count = Integer.parseInt(br.readLine());

		int[][] sum = new int[input.length + 1][26];
		for (int i = 1; i < input.length; i++) {
			for (int j = 0; j < 26; j++) {
				sum[i][j] = sum[i-1][j];
			}
			sum[i][input[i-1] - 97] = sum[i - 1][input[i-1] - 97] + 1;
		}
		
		for (int i = 0; i < sum.length; i++) {
			System.out.print(i+ " : ");
			for (int j = 0; j < 26; j++) {
				System.out.print(sum[i][j] + " ");
			}
			System.out.println();
		}
		
		for (int i = 0; i < count; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			char c = st.nextToken().charAt(0);
			int lt = Integer.parseInt(st.nextToken());
			int rt = Integer.parseInt(st.nextToken());
			int a = 0;
			if(input[rt] == c) {
				a = 1;
			}
			
			int result = sum[rt][c-97]+ a - sum[lt][c-97];
			sb.append(result+"\n");
		}

		System.out.println(sb.toString());
	}

}