[SWEA] 은기의 송아지 세기

Posted on | In |

문제 보러가기

제한사항

이외의 제한사항은 없다.

첫번째 생각

단순 구현문제라고 생각해서 코드를 작성하였다.

=> 시간초과

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T =sc.nextInt();
		for(int tc=1;tc<=T; tc++) {
			int N= sc.nextInt();
			int Q = sc.nextInt();
			
			int[] cow = new int[N];
			for(int i=0; i<N;i++) {
				cow[i] = sc.nextInt();
			}
			System.out.println("#"+tc);
			for(int i=0; i<Q; i++) {
				int start = sc.nextInt();
				int end = sc.nextInt();
				int[] count = new int[4]; // 0번 미사용
				for(int j=start-1; j<end; j++) {
					count[cow[j]]++;
				}
				System.out.println(count[1]+" "+count[2]+" "+count[3]);
			}
		}
	}
}
두번째 생각

cow_count 배열을 두어 형상관리를 한다.

cow_count[3] 이라면 3번 송아지까지의 품종을 기록한 문자열이고

cow_count[10] 이라면 10번 송아지까지의 품종을 기록한 문자열이다.

cow_count[10] - cow_count[3] 이라면 3~10번의 송아지를 찾을 수 있을 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T =sc.nextInt();
		for(int tc=1;tc<=T; tc++) {
			int N= sc.nextInt();
			int Q = sc.nextInt();
			
			int[] cow = new int[N+1];
			int[] count = new int[4]; // 0번 미사용
			String[] cow_count = new String[N+1];
			cow_count[0] = "0 0 0";
			for(int i=1; i<N+1;i++) {
				cow[i] = sc.nextInt();
				count[cow[i]]++;
				cow_count[i] = count[1]+" "+count[2]+" "+count[3]+"";
			}
			System.out.println("#"+tc);
			for(int i=0; i<Q; i++) {
				int start = sc.nextInt();
				int end = sc.nextInt();
				
				String[] send = cow_count[end].split(" ");
				String[] sstart = cow_count[start-1].split(" ");
				
				int count0 = Integer.parseInt(send[0])-Integer.parseInt(sstart[0]);
				int count1 = Integer.parseInt(send[1])-Integer.parseInt(sstart[1]);
				int count2 = Integer.parseInt(send[2])-Integer.parseInt(sstart[2]);
				
				System.out.println(count0+" "+count1+" "+count2);
			}
		}
	}
}