[구현] boj 1293 오리 java

오리 성공

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

642

226

188

35.878%

문제

오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.

영선이의 방에는 오리가 있는데, 문제를 너무 열심히 풀다가 몇 마리의 오리가 있는지 까먹었다.

갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.

녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는 두 오리가 울었다고 볼 수 있다.

영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다.

출력

영선이 방에 있을 수 있는 오리의 최소 수를 구하는 프로그램을 작성하시오. 녹음한 소리가 올바르지 않은 경우에는 -1을 출력한다.

예제 입력 1 복사

quqacukqauackck

예제 출력 1 복사

2

예제 입력 2 복사

kcauq

예제 출력 2 복사

-1

예제 입력 3 복사

quackquackquackquackquackquackquackquackquackquack

예제 출력 3 복사

1

예제 입력 4 복사

qqqqqqqqqquuuuuuuuuuaaaaaaaaaacccccccccckkkkkkkkkk

예제 출력 4 복사

10

예제 입력 5 복사

quqaquuacakcqckkuaquckqauckack

예제 출력 5 복사

3

예제 입력 6 복사

quackqauckquack

예제 출력 6 복사

-1

힌트

예제 5의 경우에 다음과 같이 오리 3마리가 울었다고 할 수 있다.

녹음: quqaquuacakcqckkuaquckqauckack
오리 1: ____q_u__a___ck_______________
오리 2: __q__u_ac_k_q___ua__ckq_u__ack
오리 3: qu_a_______c___k__qu___a_ck___

 

[문제 풀이]

1. "quack" 가 완성되어야 오리 1마리 이다.

2. HashMap을 이용하여 "quack" 를 "1 2 3 4 5"로 계산한다.

3. "q", 즉 1이 오면 Arraylist에 추가한다.

4. "q"이 외에 다른 문자가 오면, list에 현재오는 숫자보다 1이 작은 숫자, 즉 차례데로오는 숫자인지 확인하여 맞으면 그자리 숫자를 대체한다.

5. "k" 즉 숫자 5가 나오면, quack가 완성된 것이므로, 현재 오리의 수, 즉 list.size()가 오리의 수가 된다. (이후 리스트에서 제거한다.)

6. 들어오는 문자가 차례데로 오는 숫자가 아니면, 잘못들어온 소리이므로 -1을 출력한다.

7. 모든 반복문이 끝났을 때, list에 데이터가 남아있으면, 완성되지 않은 소리가 있는 것 이므로, 잘못된 소리이다.(-1)

package implementation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class boj12933_오리 {

	static ArrayList<Integer> duck = new ArrayList<Integer>();
	static int maxlength =-1;
	static HashMap<String, Integer> quack = new HashMap<String, Integer>(){{
		put("q",1);
		put("u",2);
		put("a",3);
		put("c",4);
		put("k",5);
	}};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String temp[] = br.readLine().split("");
		
		for(String s : temp) {
			int number = quack.get(s);
			boolean flag = false;
			
			//오리의 시작
			if(number==1) {
				duck.add(1);
				
			}
			
			else {
				for(int index=0;index<duck.size();index++) {
					//올바른 울음소리 순서
					if(duck.get(index) == number-1) {
						duck.set(index, number);
						if(number == 5) {
							//오리 수
							maxlength = Math.max(maxlength, duck.size());
							duck.remove(index);
						}
						
						flag = true;
						break;
					}
				}
				if(!flag) {
					System.out.print(-1);
					return;
				}
			}

		}
		
		if(duck.size()!=0)
			System.out.print(-1);
		else
			System.out.println(maxlength);
	}

}