[백준] 14713번 - 앵무새 (Java)

 

 

<문제 분석>
N마리의 앵무새가 한 문장씩 이야기 한다.
다른 앵무새가 문장을 이야기 하는 중간에 다른 앵무새가 치고 들어올 수 있다.
예제 문장이 조합이 가능하면 possible, 불가능하면 Impossible을 출력한다.

<풀이>
큐를 배열로 N개만큼 만들어서 앵무새의 문장을 단어로 잘라서 저장한다.
테스트 문장은 배열, 리스트 혹은 큐로 저장하자.
테스트 문장을 루프를 돌리면서 첫 단어를 앵무새 문장의 첫 단어에 있는지 루프를 돌리며 탐색하자.
있으면 그 단어는 삭제하고 다음으로 넘어가자. 없으면 바로 Impossible 출력한다.
테스트 문장 끝까지 무사히 탐색했으면 Possible을 출력한다.

<추가>
받아적은 문장의 단어의 수와 N개의 앵무새가 말한 단어의 수가 같아야 한다.
받아적은 문장의 단어검색이 끝났는데 앵무새의 단어가 남아있다면 Impossible을 출력하도록 하자 통과했다.

 

<코드 구현>

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;


//[백준] 14713번 - 앵무새 (Java)

public class Main {
    static int N;
    static Queue<String> Q[];
    static Queue<String> T = new LinkedList<String>();
    
    public void InputData() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        Q = new LinkedList[N];
        for (int i=0; i<N; i++) {
            Q[i] = new LinkedList<String>();
        }
        sc.nextLine();
        for (int i=0; i<N; i++) {
            String str = sc.nextLine();
            String s[] = str.split(" ");
            for (int j=0; j<s.length; j++) {
                Q[i].add(s[j]);
            }
        }
        String tmp = sc.nextLine();
        String t[] = tmp.split(" ");
        for (int i=0; i<t.length; i++) {
            T.add(t[i]);
        }
    }

	public void Solve() {
        while (!T.isEmpty()) {
            String word = T.poll();
            boolean found = false;
            for (int i=0; i<N; i++) {
                //System.out.println(word+" / "+Q[i].peek());
                if (word.equals(Q[i].peek())) {
                    Q[i].poll();
                    found = true;
                }
            }
            if (!found) { // 앵무새 한 사이클에서 찾는 단어가 없는 경우
                System.out.println("Impossible");
                return;
            }
        }
        for (int i=0; i<N; i++) { // (반례) 받아적은 단어가 앵무새 단어보다 적을 경우
            while(!Q[i].isEmpty()) {
                System.out.println("Impossible");
                return;
            }
        }
        System.out.println("Possible");
	}
    
	public static void main(String[] args)
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<제출 결과>