시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 512 MB241352615.029%

문제

승준이는 손이 도라에몽처럼 생겨서 컴퓨터로 키보드를 칠 때 오타를 많이 발생시킨다. 어느 날, 승준이는 시스템 프로그래밍 과제 점수로 F를 받게 되었다. 승준이는 도저히 이 사실이 믿기지 않아 왜 F가 나왔는지 소스코드를 다시 확인했다. 소스 코드를 본 결과 main을 mian이라고 쳐서 컴파일 에러가 난 것이다! 그래서 승준이는 소스 코드에서 이러한 오타가 더 있는지 확인을 하고 싶어졌다. 하지만 귀찮았던 나머지, 오타가 발생한 단어들을 자동으로 알고 있는 단어들 중에서 가장 유사도가 높은 단어로 바꾸는 프로그램을 작성하려 한다.

오타가 발생하는 경우 두 자판이 키보드에서 가까이 있어야 하기 때문에 두 자판 사이의 거리가 짧을수록 유사도가 높고, 멀수록 유사도가 낮다. 예를 들어 A와 S는 거리가 16밖에 되지 않지만, A와 M는 692나 된다. 따라서 S와 A의 유사도가 S와 M의 유사도보다 높은 것이다.

문자와 문자 사이의 거리는 두 문자 자판의 중심 점 사이의 유클리드 거리의 제곱으로 정의한다. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 유클리드 거리 제곱은 $(y_1 - y_2)^2 + (x_1 - x_2)^2$이다. 각 자판은 위 그림과 같이 좌표평면에 나열되어 있다. $x$좌표는 오른쪽으로 갈수록 증가하며, $y$좌표는 아래로 갈수록 증가한다. Q 자판, A 자판, Z 자판의 왼쪽 위 꼭짓점 좌표는 각각 $(0,0)$, $(1,4)$, $(3,8)$이며, 각 자판은 $4\times4$ 크기의 정사각형이다.

두 문자열 사이의 유사도를 비교하는 방법은 아래와 같다.

  1. 두 문자열에 공백을 적절히 추가해 길이를 같게 만든다. 이 때 공백은 문자열의 어디에도 추가될 수 있다.
  2. 두 문자열을 앞부터 비교해 두 문자 중 하나 이상이 공백인 경우 1600점, 두 문자가 모두 알파벳이라면 두 문자 사이의 거리만큼의 점수를 더한다.

가능한 점수의 최솟값이 낮을수록 두 문자열의 유사도가 높은 것으로 판단한다. 알고 있는 단어들 중 오타가 난 문자열 $T$와 가장 유사도가 높은 문자열을 찾는 프로그램을 작성해 승준이가 F를 받은 것을 납득할 수 있도록 만들어 보자.

입력

첫 번째 줄에는 알고 있는 단어의 개수 $N$ $(2 \le N \le 500)$이 주어지고, 이후 $N$개의 줄에 걸쳐 알고 있는 단어 $W_i$가 알파벳 대문자로 주어진다. $(1 \le |W_i| \le 500)$

알고 있는 단어들은 중복되지 않는다.

마지막으로 오타가 난 단어 $T$가 알파벳 대문자로 주어진다. $(1 \le |T| \le 500)$

출력

알고 있는 단어들 중 오타가 발생한 단어와 가장 유사도가 높은 단어를 출력한다. 만약 유사도가 같은 단어가 여럿 존재할 경우, 가장 유사도가 높은 단어들을 사전 순으로 출력한다.

예제 입력 1

3
APPLE
ORANGE
BANANA
PPLE

예제 출력 1

APPLE

출처

University > 경북대학교 > 2022 Goricon H번