[JAVA] 백준 14713 앵무새_포인터

 

문제:

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

 

 

접근 : 

 

 - 앵무새의 말을 개별적으로 모은다.

 

 - L 의 단어를 하나씩 비교하여 앵무새들이 할 말과 비교하여 없는 단어일 경우 Impossible을 반환한다.

 

 - 만약 있다면, 그 앵무새의 다음 할 말로 포인터를 옮긴다.

 

 - 모든 단어가 끝난 후에 앵무새의 말이 남아 있는지 확인한다.

 

 

 

 

코드구현 :

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        List<String[]> spells = new ArrayList<>();
        for(int i = 0 ; i < n ; i++) spells.add(br.readLine().split(" "));

        int[] flag = new int[n];
        boolean isContains = false;
        boolean ans = false;
        String[] temp;

        for(String str : br.readLine().split(" ")){
            isContains = false;
            for(int j = 0 ; j < n ; j++){
                temp = spells.get(j);
                // 이미 포인터가 끝까지 이동한 경우 다음 앵무새 말로 넘어감
                if(flag[j] == temp.length) continue;
                // 만약 앵무새말에 L 의 단어와 일치하는 경우 다음 L 단어로 이동
                isContains = temp[flag[j]].equals(str);
                if(isContains) {
                    flag[j]++;
                    break;
                }
            }
            if(!isContains) break;
        }
        //앵무새 말을 다 사용했는지 확인
        if(isContains){
            ans = true;
            for(int k = 0 ; k < n ; k++) {
                if (flag[k] < spells.get(k).length){
                    ans = false;
                    break;
                }
            }
        }
        System.out.println(ans ? "Possible" : "Impossible");
    }
}