[백준] 14713 앵무새 - 큐(Queue) + 문자열(String) JAVA

https://www.acmicpc.net/problem/14713

코드설명

큐(Queue) + 문자열(String)을 활용합니다.

 

문제에서 처음에는 HashMap을 활용해 들어온 순서대로 우선순위를 처리해야하나? 하지만 단어가 겹칠 수 있으므로 단어의 순서를 나타내는 HashMap을 그것으로 관리해야할까? 라는 고민이 들었습니다.

 

하지만, 위와 같은 방식보다 단순히 선입선출의 구조를 이용해 큐를 활용하면 문제가 훨씬 간단해집니다.

문제를 읽어보면, 각 단어가 주어진 문자열의 "순서대로" 처리되어야 한다는 것을 알 수 있습니다.

이러한 특성을 이해하면 되겠지요.

 

시간복잡도가 걱정될 수 있습니다. 시간복잡도는 O(N) * O(L의 단어개수) 로 총 10^7 입니다. 그러므로 시간복잡도는 안전합니다. 

 

문제에서 "Impossible"을 출력하는 과정에 대해 명확히 해보면,

1. 큐에 남은 문자열이 없어야 한다. (즉, 앵무새가 말한 모든 단어를 순서대로 받아적었다.)

2. 자신이 더 많이 작성했으면 안된다. (즉, 앵무새가 말한적 없는 단어를 초과해서 작성하면 안된다. 이 때문에 단순히 Queue에 값이 비었는지 비어있지 않은지로 판단하면 안됩니다.)

코드

정답코드1입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static StringBuilder sb = new StringBuilder();
	static Queue<String>[] q = new LinkedList[101];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<101; i++) {
			q[i] = new LinkedList<String>();
		}
		
		N = Integer.parseInt(st.nextToken());
		for(int i=0; i<N; i++) {
			String str = br.readLine();
			String[] split = str.split(" ");
			
			for(int j=0; j<split.length; j++) {
				q[i].add(split[j]);
			}
		}
		
		String L = br.readLine();
		String[] split = L.split(" ");
		boolean wholeFlag = true;
		for(int i=0; i<split.length; i++) {
			boolean successFlag = false;
			for(int j=0; j<N; j++) {
				if(!q[j].isEmpty() && q[j].peek().equals(split[i])) { //만약 일치한다면, 
					q[j].poll();
					successFlag = true;
					break;
				}
			}
			
			if(successFlag == false) {
				wholeFlag = false;
				break;
			}
		}
		
		 // 모든 앵무새의 큐가 비어있는지 확인
        for(int i=0; i<N; i++) {
            if(!q[i].isEmpty()) {
                wholeFlag = false;
                break;
            }
        }
        
		if(wholeFlag == true) System.out.println("Possible");
		else System.out.println("Impossible");
		
	}

}

 

처음 오답코드입니다.

정답코드1과 무엇이 다를까요? 바로 모든 앵무새의 큐가 비어있는지 확인하는 과정입니다.

만약, 모든 앵무새가 말한 단어들을 제대로 받아적지 못한 경우에도 올바른 경우가 아닌 것 입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static StringBuilder sb = new StringBuilder();
	static Queue<String>[] q = new LinkedList[101];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<101; i++) {
			q[i] = new LinkedList<String>();
		}
		
		N = Integer.parseInt(st.nextToken());
		for(int i=0; i<N; i++) {
			String str = br.readLine();
			String[] split = str.split(" ");
			
			for(int j=0; j<split.length; j++) {
				q[i].add(split[j]);
			}
		}
		
		String L = br.readLine();
		String[] split = L.split(" ");
		boolean wholeFlag = true;
		for(int i=0; i<split.length; i++) {
			boolean successFlag = false;
			for(int j=0; j<N; j++) {
				if(!q[j].isEmpty() && q[j].peek().equals(split[i])) { //만약 일치한다면, 
					q[j].poll();
					successFlag = true;
					break;
				}
			}
			
			if(successFlag == false) {
				wholeFlag = false;
				break;
			}
		}
        
		if(wholeFlag == true) System.out.println("Possible");
		else System.out.println("Impossible");
		
	}

}