[Baekjoon 28432] 끝말잇기 | Python

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

---

문제

 

끝말잇기를 한 단어들이 주어지고, 그 중 ? 에 해당하는 단어를 찾는 문제이다.

후보군 중에서 끝말잇기 조건인 앞 단어의 가장 뒷 글자를 첫 글자로 가지면서, 뒷 단어의 가장 앞 글자를 마지막 글자로 가지는 단어를 찾아야 한다.

단 끝말잇기에 사용된 단어는 ? 가 될 수 없다.

 

---

풀이

 

조건을 만족하기 위해 ? 가 등장하는 위치를 찾고 그 앞 단어의 가장 뒷 글자와 그 뒷 단어의 가장 앞 글자를 알아낸다. 단 ? 가 가장 앞에 주어지거나 가장 뒤에 주어지는 경우에는 앞 단어나 뒷 단어가 없으므로 주의해야 한다.

이때 경우의 수가 다음과 같이 여러 개로 나뉘어 진다.

• 끝말잇기 단어가 ? 하나이고, 후보 단어도 하나인 경우

• 이 경우에는 문제의 답이 정확히 하나인 경우만 입력으로 주어진다고 하였으므로 후보 단어로 나온 단어 하나가 ? 에 해당하는 단어이다.

• 예제처럼 일반적인 경우

• ? 의 가장 앞 글자와 가장 뒷 글자를 구한다. 그 후에 후보 단어 중에 앞 글자와 뒷 글자가 만족하는 단어를 찾으면 된다. 단 해당 후보 단어가 끝말잇기에 사용된 단어면 안된다.

• ? 가 시작이나 끝인 경우

• ? 가 가장 앞에 주어진 경우는 ? 의 앞 글자를 고려하지 않는다. ? 가 가장 뒤에 주어진 경우는 ? 의 뒷 글자를 고려하지 않는다. 이를 유의해서 후보 단어 중 조건에 만족하는 단어를 찾아낸다.

아래 코드에서는 ? 의 위치를 파악하고, 위치를 나타내는 인덱스가 0 인 경우는 앞 단어가 없는 경우로, 인덱스가 가장 마지막인 경우는 뒷 단어가 없는 경우로 처리하였다.

좀 더 효율적으로 구성하려면 후보 단어가 끝말잇기에 사용된 단어에 있는지 확인할 때 끝말잇기에 사용된 단어를 리스트가 아니라 딕셔너리로 만들어서 확인하면 해시 테이블을 사용하여 확인하기 때문에 더 빠르게 확인할 수 있을 것 같다. 단 이 문제에 경우 리스트로 만들어서 확인해도 충분히 빨랐기 때문에 리스트를 사용하였다.

 

---

코드

 

words = []
candidates = []
point = 0
word_n = int(input())
for i in range(word_n):
    words.append(input())
    if words[i] == '?':
        point = i
candidate_n = int(input())
for _ in range(candidate_n):
    candidates.append(input())
if point > 0:
    start = words[point-1][-1]
if point < word_n-1:
    end = words[point+1][0]
if word_n == 1 and candidate_n == 1:
    print(candidates[0])
elif point > 0 and point < word_n-1:
    for candidate in candidates:
        if candidate.startswith(start) and candidate.endswith(end) and candidate not in words:
            print(candidate)
            break
elif point > 0:
    for candidate in candidates:
        if candidate.startswith(start) and candidate not in words:
            print(candidate)
            break
else:
    for candidate in candidates:
        if candidate.endswith(end) and candidate not in words:
            print(candidate)
            break