[백준 28432] 끝말잇기

문제 출처 : https://www.acmicpc.net/problem/28432

 

문제 이해하기

끝말잇기를 하기 위해서 앞의 단어의 마지막 글자와 다음 단어의 첫 번째 글자를 알아야 합니다. 그리고 그 문자가 끝말잇기 리스트에 포함되서는 안됩니다. 여기서 또 한가지 문제는 ?가 맨 처음에 위치할 수도 있고, 마지막에 위치할 수도 있다는 것입니다. 따라서 처음과 마지막일 경우의 처리도 생각하면서 문제를 해결해야 합니다. 우리가 고려해야할 사항을 적어보았습니다.

1. ?가 처음에 위치할 경우
2. ?가 마지막에 위치할 경우
3. 문자중에 ?가 있는지 확인

위 세 가지를 고려해서 문제를 해결해 보겠습니다.

코드 작성

그럼 코드를 작성해 보겠습니다.

입력 받기

N = int(input())
S = []

idx = 0
for i in range(N):
    s = input()
    if s == "?":
        idx = i
    S.append(s)

M = int(input())
A = []
for _ in range(M):
    A.append(input())

끝말잇기 기록의 길이 N을 입력 받습니다. 그리고 N개 만큼의 끝말잇기 기록 S를 입력 받습니다. 이 때 ?의 위치를 찾기 위해 s가 ?인 경우 idx에 그 인덱스 값 i를 저장 합니다.

다음으로 후보 단어의 개수 M을 입력 받습니다. 그리고 A에 후보 단어들을 저장 합니다.

첫 번째 글자, 마지막 글자 찾기

first_ch, last_ch = '', ''
if idx != 0:
    first_ch = S[idx - 1][-1]
if idx != N - 1:
    last_ch = S[idx + 1][0]

끝말잇기의 첫 번째 글자인 first_ch와 마지막 글자인 last_ch를 찾습니다. 이 때 ?의 위치인 idx의 값이 맨 앞에 위치할 수도 있고, 맨 마지막에 위치할 수도 있습니다. 맨 앞에 있는 경우 첫 번째 글자는 아무거나 와도 되기 때문에 빈칸이 됩니다. 맨 앞에 있는 것이 아니라면 idx의 앞의 단어의 마지막 글자가 fist_ch가 됩니다. 따라서 idx의 앞에 있는 단어의 마지막 글자인 S[idx - 1][-1]이 됩니다.

마찬가지로 idx값이 마지막인 경우 last_ch가 아무거나 와도 됩니다. 그렇지 않다면 idx의 다음 단어의 첫 번째 글자가 됩니다. 따라서 last_ch는 S[idx + 1][0]이 됩니다.

문제 해결하기

def solve(w):
    if (w[0] == first_ch or first_ch == '') and (w[-1] == last_ch or last_ch == ''):
        if w not in S:
            print(w)
            return True
    return False

for w in A:
    if solve(w):
        break

후보 단어 A를 모두 뒤져가며 그 단어가 끝말잇기에 적합한지 확인합니다. 문제에서 답은 하나밖에 없다고 하였기 때문에 solve() 함수로 문제를 해결하면 바로 빠져나오면 됩니다.

solve 함수는 단어가 끝말잇기에 적합한지 찾습니다. 먼저 맨 앞의 글자가 first_ch와 같은지 확인합니다. 그리고 마지막 글자와 last_ch와 같은지 확인 합니다. 앞에서 언급했듯이 first_ch, last_ch가 빈 값이면 어떤 값이 와도 상관 없습니다.

만역 위의 조건에 만족한다면 해당 단어가 S에 속해있는지 확인합니다. 만약 S에 없다면 그 값을 출력하고 종료합니다.

조금이라도 빠른 코드를 만들기 위해서는 먼저 앞 뒤 글자를 확인하고 S에 있는지 없는지 판단하는 것이 좋습니다. S의 크기가 100개밖에 되지 않기 때문에 크게 상관은 없지만 조건에 부합하지 않는 단어를 모두 포함되는지 확인할 필요는 없습니다.

만약 S의 크기가 더 크다면 S를 정렬한 뒤 찾는 것이 좀 더 빠르게 만들 수 있습니다.

전체 코드

전체 코드를 확인해 보겠습니다.

N = int(input())
S = []

idx = 0
for i in range(N):
    s = input()
    if s == "?":
        idx = i
    S.append(s)

M = int(input())
A = []
for _ in range(M):
    A.append(input())

first_ch, last_ch = '', ''
if idx != 0:
    first_ch = S[idx - 1][-1]
if idx != N - 1:
    last_ch = S[idx + 1][0]

def solve(w):
    if (w[0] == first_ch or first_ch == '') and (w[-1] == last_ch or last_ch == ''):
        if w not in S:
            print(w)
            return True
    return False

for w in A:
    if solve(w):
        break