백준 12933 - 오리

Java

12933 번 - 오리

문제

접근 방법

오리를 나타낼 Stack을 여러개 담을 List를 선언하였다. 전체 울음 소리를 앞에서 부터 탐색하여, 현재 단어를 이전 단어 뒤에 넣을 곳을 찾아 하나씩 삽입한다.
예를들어, 현재 리스트에 [['q','u','a'],['q','u'],['q']] 이렇게 되어 있으면, 현재 오리는 3마리이다.
넣을 문자가 ‘c’이면 제일 첫번째 오리에, ‘a’이면 2번째 오리에 add하는 방식으로 오리의 울음 소리들을 분류한다.

만약 위와 같은 예에서 ‘k’ 문자를 넣을 곳이 없는데 울음 소리에서 해당 문자가 나오면, 잘 못된 울음소리라고 판단하여 -1을 출력하고 종료한다.

여기까지가 처음에 내가 생각했던 방식이었다.
예제는 잘 통과하였는데, 64% 에서 실패하였다.
다른 사람의 코드를 참고하니, 빠트린 것이 있는데 바로, 모든 오리라 ‘quack’를 완벽히 갖추었는 가를 생각하지 못하였다.

따라서, ‘q’,’u’,’a’,’c’,’k’가 나올 때 마다 각각 개수를 세 마지막에 5의 배수인지, 각 문자가 나온 개수가 같은지 확인해 주는 과정을 거치니 통과하였다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static List<Stack<Character>> dock;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	String str = br.readLine();

    	dock = new ArrayList<>();
    	int[] dockCnt = new int[5];
    	char curC;
		// 울음소리 탐색 시작
    	for(int i = 0; i < str.length(); i++) {
    		curC = str.charAt(i);

    		switch(curC) {
    		case 'q':
    			dockCnt[0]++;
				// 아직 오리가 한마리도 없을 때
    			if(dock.isEmpty()) {
    				dock.add(new Stack<Character>());
    				dock.get(0).add('q');
    			}
    			else if(!findLoc('k', 'q')) {
    				dock.add(new Stack<Character>());
    				dock.get(dock.size() - 1).add('q');
    			}
    			break;
    		case 'u':
    			dockCnt[1]++;
    			if(!findLoc('q', 'u')) {
    				System.out.println(-1);
    				return;
    			}
    			break;
    		case 'a':
    			dockCnt[2]++;
    			if(!findLoc('u', 'a')) {
    				System.out.println(-1);
    				return;
    			}
    			break;
    		case 'c':
    			dockCnt[3]++;
    			if(!findLoc('a', 'c')) {
    				System.out.println(-1);
    				return;
    			}
    			break;
    		case 'k':
    			dockCnt[4]++;
    			if(!findLoc('c', 'k')) {
    				System.out.println(-1);
    				return;
    			}
    			break;
    		}
    	}
		// 총 문자의 수
    	int totalDock = 0, qCnt = dockCnt[0];
    	boolean isOk = true;
		// 각 문자의 수가 다르면 실패
    	for(int i = 0; i < 5; i++) {
    		totalDock += dockCnt[i];
    		if(qCnt != dockCnt[i]) {
    			isOk = false;
    			break;
    		}
    	}
    	if(totalDock % 5 != 0)
    		isOk = false;

    	if(isOk)
    		System.out.println(dock.size());
    	else
    		System.out.println(-1);
    	br.close();
	}
	// 현재 문자를 적합한 오리에 넣어주는 함수
	// 만약, 적합한 곳이 없으면 false를 반환해 실패하게 하였다.
	static boolean findLoc(char lastC, char curC) {
		for(int i = 0; i < dock.size(); i++) {
			if(dock.get(i).peek() == lastC){
				dock.get(i).add(curC);
				return true;
			}
		}
		return false;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

쉬운 문제였는데, 오래 걸렸다.

개선할 점