[BOJ/백준] 28432 - 끝말잇기

28432번: 끝말잇기

---

?가 처음 단어인지, 끝 단어인지, 중간 단어인지

그리고 중복이 없는 지

---

---

• 제목

끝말잇기

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

끝말잇기는 단어를 중복하지 않고 단어의 맨 끝 글자에 이어서 말하는 놀이입니다. 끝말잇기 기록은 단어들의 나열로 이루어집니다. 올바른 끝말잇기 기록은 각 단어의 마지막 글자가 다음 단어의 첫 글자이며, 단어가 중복되어서 나타나면 안 됩니다.

끝말잇기 기록이 주어지는데, 하나의 기록은 “?”로 가려진 채로 들어옵니다. “?”에 들어갈 수 있는 문자열들의 후보가 주어질 때, 올바른 끝말잇기 기록을 만드는 “?”에 들어갈 문자열을 출력하세요.

---

• 입력

첫 줄에 끝말잇기 기록의 길이 N 이 주어집니다. (1 ≤ N ≤ 100)(1 ≤ N ≤ 100) 둘째 줄부터 다음 N개의 줄에는 끝말잇기의 기록 S_1, ..., S_N이 한 줄에 하나씩 주어집니다. 여기서, 하나의 S_i는 “?” 로 주어집니다. 나머지 S_i는 길이 2 이상 10 이하의 영어 소문자로 이루어진 문자열입니다.

다음 줄에 후보 단어의 개수 M이 주어집니다. (1 ≤ M ≤ 100)(1 ≤ M ≤ 100) 다음 M개의 줄에는 후보 단어 A_1, ..., A_M이 주어집니다. A_i는 길이 2 이상 10 이하의 영어 소문자로 이루어진 문자열입니다. A_1, ..., A_M은 서로 다릅니다.

문제의 답이 정확히 하나인 경우만 입력으로 주어집니다.

---

• 출력

“?”에 들어갈 수 있는 문자열을 후보 단어인 A_1, ..., A_M 중에서 하나 찾아서 출력하세요.

---

예제 입력1	예제 출력1
5 charlie echo ? romeo oscar 3 alfa oscar or	or

---

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Set<String> previous = new HashSet<String>();
        int N = Integer.parseInt(br.readLine());
        int idx = -1;
        String[] arr = new String[N];
        for(int i = 0; i < N; i++){
            String word = br.readLine();
            if(!"?".equals(word)) previous.add(word);
            else idx = i;
            arr[i] = word;
        }
        int M = Integer.parseInt(br.readLine());
        for(int i = 0; i < M; i++){
            String word = br.readLine();
            if(N == 1) {
                System.out.println(word);
                break;
            };
            if(previous.contains(word)) continue;
            if(idx == 0){
                if(arr[idx + 1].charAt(0) == word.charAt(word.length() - 1)){
                    System.out.println(word);
                    break;
                }
            }
            else if(idx == N - 1){
                if(arr[idx - 1].charAt(arr[idx - 1].length() - 1) == word.charAt(0)){
                    System.out.println(word);
                    break;
                }
            }
            else{
                if(arr[idx + 1].charAt(0) == word.charAt(word.length() - 1)
                        && arr[idx - 1].charAt(arr[idx - 1].length() - 1) == word.charAt(0)){
                    System.out.println(word);
                    break;
                }
            }
        }
    }
}