[JAVA] [SW Expert] 7088. 은기의 송아지 세기

프로그래밍 대회를 성공적으로 마친 은기는 사회 공헌을 위해 대회 우승자들과 농촌 봉사활동을 떠나기로 했다.

은기와 대회 우승자들은 한적한 시골 마을 어딘가에 N마리의 송아지를 키우고 있는 곳으로 갔다.

그 곳의 각 송아지에는 1번부터 N번까지의 고유번호와 1번부터 3번까지의 품종 번호가 매겨져 있었다.

은기와 대회 우승자들은 송아지들을 보고서 문득 질문이 생겼다.

        “고유번호 L번부터 R번까지의 송아지들에 대해서 각각의 품종은 몇 마리가 있을까?”

이들이 궁금해하는 모습을 본 당신은, 프로그램을 만들어 도와주기로 결정하였다.

질문 Q개에 대하여 각각 1번, 2번, 3번 품종의 수를 답해주는 프로그램을 작성하라.

 

이 문제의 경우 단순히 모든 것을 입력받고 1번부터 N번까지의 for문을 돌면서 숫자들을 세어 각 품종의 수를 출력하면 된다고 생각을 할 수 있지만 N 과 Q 가 최대 100,000 이고

 

N이 10만일때 Q 또한 10만 그리고 Q 의 범위가 N이게 되면 10만 * 10만^Q 승이 되기때문에 무수히 많은 for문을 돌게 된다.

 

따라서 1부터 N 까지 배열을 3개 만들고( 2차원 배열로 만들어도 무관하다 ) 입력시 k번째에는 1부터 k번째 까지 몇마리의 송아지가 몇번 품종인지를 메모이제이션을 통해서 저장하고 출력하면 된다.

 

완성된 코드는 다음과 같다 코드만 본다면 바로 이해갈 것이다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Solution {
	static int N;
	static int Q;
	static int[] oneCow;
	static int[] twoCow;
	static int[] threeCow;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		String[] s = null;
		for(int t=1; t<=T; t++) {
			s = br.readLine().split(" ");
			N = Integer.parseInt(s[0]);
			Q = Integer.parseInt(s[1]);
			oneCow = new int[N+1];
			twoCow = new int[N+1];
			threeCow = new int[N+1];
			int num = 0;
			for(int i=1; i<=N; i++) {
				num = Integer.parseInt(br.readLine());
				if(num == 1) {
					oneCow[i] = oneCow[i-1]+1;
					twoCow[i] = twoCow[i-1];
					threeCow[i] = threeCow[i-1];
				}else if(num == 2) {
					oneCow[i] = oneCow[i-1];
					twoCow[i] = twoCow[i-1]+1;
					threeCow[i] = threeCow[i-1];
				}else if(num == 3) {
					oneCow[i] = oneCow[i-1];
					twoCow[i] = twoCow[i-1];
					threeCow[i] = threeCow[i-1] + 1;
				}
			}
			int ff = 0;
			int ss = 0;
			bw.write("#"+t+"\n");
			for(int i=0; i<Q; i++) {
				s = br.readLine().split(" ");
				ff = Integer.parseInt(s[0])-1;
				ss = Integer.parseInt(s[1]);
				bw.write(""+(oneCow[ss]-oneCow[ff])+" "+(twoCow[ss]-twoCow[ff])+" "+(threeCow[ss]-threeCow[ff])+"\n");
			}
		}
		br.close();
		bw.close();
	}
}