문제
6개의 3글자 단어가 주어진다. 이 중 3개를 골라 3x3 격자의 가로줄에 배치했을 때, 세로줄로 읽은 3개의 단어도 나머지 3개와 일치하는 배치를 찾아라.
입력
6개의 3글자 단어가 한 줄에 하나씩 주어진다.
출력
3x3 격자를 출력한다. 불가능하면 0을 출력한다. 여러 답이 있으면 사전순으로 가장 빠른 것을 출력한다.
예제
| 입력 | 출력 |
|---|---|
AAB ABA ABB BAA BAB BBA | AAB BAA BBA |
풀이
6개 단어 중 3개를 가로줄로 선택하고, 세로줄로 만들어지는 3개의 단어가 나머지와 일치하는지 확인하는 브루트포스 방식이다.
- 6개 단어를 사전순 정렬한다
- 3중 반복문으로 서로 다른 3개의 단어를 가로줄로 선택한다
- 선택한 가로 3줄에서 세로 3개의 단어를 만든다
- 가로 3개 + 세로 3개를 합친 후 정렬했을 때 원래 6개 단어와 일치하는지 확인한다
- 일치하면 결과 리스트에 추가하고, 사전순으로 가장 빠른 것을 출력한다
핵심 아이디어: 6개 중 3개를 선택하는 경우의 수는 6P3 = 120가지로 매우 적다. 가로 + 세로 6개 단어를 정렬하여 원본과 비교하면 유효한 배치를 판별할 수 있다.
코드
arr = [input() for _ in range(6)]
arr.sort()
ans_list = []
for i in range(6):
for j in range(6):
for k in range(6):
if i == j or i == k or j == k:
continue
temp = [arr[i], arr[j], arr[k]]
temp2 = temp.copy()
for h in range(3):
temp2.append(temp[0][h] + temp[1][h] + temp[2][h])
temp2.sort()
if arr == temp2:
ans_list.append(temp[0] + temp[1] + temp[2])
ans_list.sort()
if len(ans_list):
for i in range(0, 10, 3):
print(ans_list[0][i : i + 3])
else:
print(0)복잡도
- 시간: O(6^3) — 6개 단어에서 3개를 순열로 선택하는 완전 탐색
- 공간: O(1) — 결과 저장 외 추가 공간 미미