[SWEA] 5550. 나는 개구리로소이다

문제

개구리 한 마리가 한번 울면 “croak”하는 소리가 난다. 개구리 한 마리가 계속 여러 번 울면 울음소리가 다음처럼 나타날 수 있다.

“croakcroak”, “croak”, “croakcroakcroakcroak”

영은이는 개구리를 연구하기 위해 많은 개구리를 사육한다. 영은이는 개구리들을 키우는 우리에 들어와 울음소리를 녹음했다.

여러 개구리가 동시에 울면 울음소리가 섞여서 녹음된다.

이 때 한 개구리의 울음소리는 녹음된 울음소리에서 부분 문자열로 나타난다. 이 부분 문자열은 연속하지 않아도 된다. 예를 들어 "crcoarkcoroakak"와 같을 수 있다.

그렇다면, 녹음을 할 때 있었던 개구리는 최소 몇 마리일까?

 

풀이방법

최소 개구리의 수를 구하기 위해서 다음과 같은 조건을 만족해야한다.

 

1) 개구리는 'c', 'r', 'o', 'a', 'k' 순서대로 운다

 

2) 개구리는 여러번 울 수 있다.

 

3) 개구리는 'c', 'r', 'o', 'a' ,'k'를 전부다 말해야한다.

 

문자를 카운팅할 수 있는 배열을 만들고 위의 조건을 만족하는지 확인한다.

 

예를 들어 crcoarkcoroakak이 입력으로 주어진다.

위와 같은 사이클로 개구리 수를 찾는다. 

 

그렇다면 개구리 수가 존재하지 않는 경우를 찾아보자

 

소스코드

package samsung;

import java.util.*;

public class s_5550 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] flog = {'c', 'r', 'o', 'a', 'k'};
		int tc = sc.nextInt();
		for(int t = 1; t <= tc; t++) {
			String s = sc.next();
			int[] a = new int[5];
			int flag = 0;
			int max = 0;
			
			for(int i = 0; i < s.length(); i++) {
				max = Math.max(a[0], max);
				
				for(int j = 0; j < 5; j++) {
					if(s.charAt(i) == flog[j]) {
						a[j]++;
						if(j > 0 && a[j] > a[j-1]) {
							flag = 1;
							break;
						}
						if(j == 4) {
							for(int k = 0; k < 5; k++) {
								a[k]--;
							}
						}
					}
				}
			}
			for(int i = 0; i < 5; i++) {
				if(a[i] != 0) {
					flag = 1;
					break;
				}
			}
			if(flag == 0)
				System.out.println("#" + t + " " + max);
			else
				System.out.println("#" + t + " " + (-1));
		}
	}
}