[백준] 단계별로 풀어보기(단계:16, 누적합,JAVA)16139번, 인간-컴퓨터 상호작용

 

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

누적합이란?

입력되는 값들의 누적합 값을 따로 저장하여 필요에 따라 사용하는 알고리즘입니다.

 

예를 들어 1 5 4 36 8이 입력되었을 때 누적합 값을 저장한 배열을 표로 표현하면

	1	5	4	36	8
누적합	1	6	10	46	54

이 문제에 핵심은

1. 문자열 S에서 질문에 주어지는 알파벳이 해당 범위에 존재하는 개수를 결과로 출력해야합니다.

2. 알파벳은 소문자만 제공됩니다.

 

저는 이 문제를 누적합을 이용하여 간단하게 해결하였습니다.

 

시간 복잡도에 관해서 생각하여 모든 알파벳의 누적합을 구한 뒤에 질문에 대답하였습니다.

 

사용한 배열

 

DP[][26] : 누적합 저장 배열

 

DP[i][j]는 i번째 문자열값까지의 j번째 알파벳에 누적합을 가르킵니다.

26으로 초기화하는 이유는 알파벳에 개수가 25개이기 때문입니다.

 

예제입력 1에서 문자열에 대한 알파벳 a에 대한 누적합을 표로 나타내면 (DP[][0])

	s	e	u	n	g	j	a	e	h	w	a	n	g
누적합	0	0	0	0	0	0	1	1	1	1	2	2	2

 

알파벳 s에 대한 누적합을 표로 나타내면 (DP[][18])

	s	e	u	n	g	j	a	e	h	w	a	n	g
누적합	1	1	1	1	1	1	1	1	1	1	1	1	1

 

알파벳 a에 대한 질문을 받았을 때를 수행하면

l = 0, r = 6이면

seungj로써 결과로 0이 출력됩니다.

 

l = 4, r = 8이면

gjaeh로써 결과로 1이 출력됩니다.

 

여기서 규칙을 발견하실 수 있습니다.

 

l == 0일 때

개수 = DP[r][j]

 

l > 0일 때

개수 = DP[r][j] - DP[l-1][j]

 

규칙을 적용해보면알파벳 a를 찾고 l = 2, r = 8이면

개수 = DP[4][0] - DP[1][0] = 1 - 0 = 1

 

알파벳 s를 찾고 l = 0, r = 5이면

개수 = DP[5][18] = 1 

 

위에 규칙을 통해 나오는 누적합을 질문마다 출력하면 됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 S, q와 q개의 질문을 받습니다.

2. 문자열 S에 대한 모든 알파벳에 누적합 DP[][]를 구성합니다.

3. q에 질문에 대하여 규칙을 사용하여 누적합을 구해서 결과로 출력합니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 q개의 질문을 분리하였습니다.
• 문자열 S에 대한 모든 알파벳에 누적합을 DP[][]에 저장하였습니다.
• 질문에 범위에 대한 알파벳에 개수를 구하는 cal 함수를 만들었습니다.
• BufferedWriter에 질문에 알파벳 개수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal은 규칙과 DP 배열을 이용하여 해당 범위에 알파벳 개수를 구해서 반환하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static String S;		//문자열 저장 변수
	static int q;		//질문 개수 저장 변수
	static int[][] DP = new int[200002][26];	//누적합 저장 배열
	public static void main(String[] arg) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		S = br.readLine();
		q = Integer.parseInt(br.readLine());
        	//-----각 알파벳 문자열에 대한 누적합 구하기------
		for(int i=0;i<=25;i++) {
			for(int j=1;j<=S.length();j++) {
				if(S.charAt(j-1) + 0 == 'a' + i) {
					DP[j][i] = DP[j-1][i] + 1;	//문자열에 문자 해당 알파벳일 때
				}else
					DP[j][i] = DP[j-1][i];	//문자열에 문자 해당 알파벳 아닐 때
			}
		}
		StringTokenizer st;
       	 	//질문 값 저장 및 함수 실행하여 결과 BufferedWriter 저장
		for(int i=0;i<q;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int alphabet = st.nextToken().charAt(0) - 97;
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			bw.write(cal(alphabet,start,end) + "\n");
		}
		
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//규칙을 적용하여 알파벳 개수 구하는 함수
	static int cal(int alphabet, int start, int end) {
		int result;
		if(start == 0)
			result = DP[end+1][alphabet];	//l == 0일 때
		else		//l > 0일 때
			result = DP[end+1][alphabet] - DP[start][alphabet];
		
		return result;
	}
}