[백준 / Python 파이썬] 25328번 - 문자열 집합 조합하기

[Silver III] 문자열 집합 조합하기 - 25328

---

문제 링크

분류

백트래킹, 브루트포스 알고리즘, 자료 구조, 해시를 사용한 집합과 맵, 문자열

문제 설명

알파벳 소문자로 구성된 문자열 X, Y, Z가 주어진다. 각각의 문자열에는 중복된 문자가 존재하지 않는다. 문자열 S에 있는 문자 중 임의로 k개를 선택하여 문자열 S에서의 순서를 유지하여 만든 모든 부분 문자열을 모아 놓은 집합을 문자열 S에 대한 조합 C(S, k)라고 하자. 예를 들어, 문자열 S = 'abc'에 대한 조합 C(S, 2) = {'ab', 'ac', 'bc'}이다. 입력으로 문자열 X, Y, Z와 정수 k가 주어질 때 C(X, k), C(Y, k), C(Z, k)에 두 번 이상 나타나는 부분 문자열을 오름차순으로 출력하자.

입력

첫 번째 줄에 문자열 X가 주어진다.

두 번째 줄에 문자열 Y가 주어진다.

세 번째 줄에 문자열 Z가 주어진다.

네 번째 줄에 정수 k가 주어진다.

출력

C(X, k), C(Y, k), C(Z, k)에 두 번 이상 나타나는 부분 문자열을 오름차순으로 출력한다. 한 줄에 하나의 부분 문자열을 출력한다. 두 번 이상 나타나는 부분 문자열이 없으면 -1을 출력한다.

---

import sys
from itertools import combinations
input = sys.stdin.readline

words = [input().strip() for _ in range(3)]
k = int(input())

temp = dict()
result = dict()
for word in words:
    for w in combinations(word, k):
        answer = "".join(w)
        if answer in temp:
            result[answer] = 1
        else:
            temp[answer] = 1


if result:
    result = sorted(result.items())
    for r in result:
        print(r[0])
else:
    print(-1)