[백준 / Python 파이썬] 25957번 - 단어 우월 효과 (캠브릿지 대학의 연구결과)

[Silver II] 단어 우월 효과 (캠브릿지 대학의 연구결과) - 25957

---

문제 링크

성능 요약

메모리: 66836 KB, 시간: 472 ms

분류

자료 구조, 해시를 사용한 집합과 맵, 정렬, 문자열, 트리를 사용한 집합과 맵

문제 설명

캠릿브지 대학의 연결구과에 따르면, 한 단어 안에서 글자가 어떤 순서로 배되열어 있는지는 중요하지 않고, 첫 번째와 마지막 글자가 올바른 위치에 있는 것이 중하요다고 한다. 나머지 글들자은 완전히 엉진망창의 순서로 되어 있라을지도 당신은 아무 문제 없이 이것을 읽을 수 있다. 왜하냐면, 인간의 두뇌는 모든 글자를 하하나나 읽는 것이 아니라 단어 하나를 전체로 인하식기 때이문다.

그렇다, 우리는 이렇게 단어의 순서가 섞어여있도 이 지문을 아지렇무도 않게 읽을 수 있다. 그래서 우리는 이으것로 문제를 내기로 했다.

문제는 간하단다. 어떤 문장을 구성할 수 있는 문자의 순서가 섞이지 않은 N개의 단들어이 주진어다. 그리고 이 N개의 단어들을 이용해 만들어진 문장 S가 주어진다. 단, S를 구하성는 각 단어는 맨 앞 문자와 맨 뒤 문자가 고정된 채 나머지 문자들은 무위작로 배열될 수 있다. 예를 들어, “캠브릿지” ⇒ “캠릿브지” 와 같은 식이다.

 N개의 단어는 모두 사용될 수도, 사용되지 않는 단어가 있을 수도, 여러 번 사용되는 단어가 있을 수도 있다.

이런 식으로 각 단어가 섞인 문장 S가 주어질 때 문장 S를 섞이지 않은 형태로 다시 배하열여 출하시력오.

입력

첫째 줄에는 원래 문장에 쓰인 단어의 수 N이 주어진다. (1≤N≤2000001≤≤200000)

두 번째 줄부터 N개의 줄에 단어가 주어진다. 각 단어의 길이는 11 이상 88 이하이다. 중복된 단어는 주어지지 않으며, 원래 단어를 하나로 정할 수 없는 경우는 주어지지 않는다. (즉, 맨 앞 문자와 맨 뒤 문자를 제외한 나머지 문자들의 배열만 다른 단어는 주어지지 않는다.)

 (N+2)(+2)째 줄에는 문장 S에 들어있는 단어의 수 M이 주어진다. (1≤M≤2000001≤≤200000)

마지막 줄에는 총 M개의 섞여 있는 단어로 이루어진 문장 S가 주어진다. 각 단어는 공백으로 구분되어 있다.

출력

첫 번째 줄에 문장의 각 단어의 문자 순서를 원래대로 배치한 결과를 출력하시오.

---

import sys
input = sys.stdin.readline


def word_trans(w):
    if len(w) > 2:
        wm = sorted(w[1:-1])
        w = w[0] + "-" + w[-1] + "-" + "".join(wm)
    elif len(w) == 2:
        w = w[0] + "-" + w[1]
    return w


N = int(input())

words = dict()
for _ in range(N):
    word = input().strip()
    new_word = word_trans(word)

    if new_word not in words:
        words[new_word] = word

M = int(input())
words_s = list(input().split())

for i in range(M):
    answer = word_trans(words_s[i])
    words_s[i] = words[answer]

result = " ".join(words_s)
print(result)