BOJ 1622 - 공통 순열

문제

두 문자열이 주어질 때, 두 문자열 모두의 어떤 순열의 부분 문자열이 될 수 있는 가장 긴 문자열을 구하라.

입력

여러 테스트 케이스가 주어지며, 각 케이스는 두 줄에 걸쳐 소문자 문자열이 주어진다.

출력

각 테스트 케이스에 대해 가장 긴 공통 순열을 알파벳 순으로 출력한다.

예제

입력	출력
`pretty` `women`	`e`

풀이

두 문자열에서 공통으로 등장하는 문자의 최소 등장 횟수만큼 결과에 포함시킨다.

두 문자열의 문자 집합의 교집합을 구한다
교집합의 각 문자에 대해 두 문자열에서의 등장 횟수 중 최솟값만큼 해당 문자를 추가한다
결과를 알파벳 순으로 정렬하여 출력한다
EOF까지 반복한다

핵심 아이디어: 공통 순열은 각 문자를 두 문자열 모두에서 가져올 수 있어야 하므로, 문자별 최소 등장 횟수가 상한이 된다.

코드

while True:
    try:
        a = input()
        b = input()
 
        a_set = set(a)
        b_set = set(b)
 
        x = a_set & b_set
 
        answer = []
        for w in x:
            a_count = a.count(w)
            b_count = b.count(w)
            answer.append(w * min(a_count, b_count))
 
        answer.sort()
        print("".join(answer))
    except:
        break

복잡도

시간: O(T * (A + B)) (T는 테스트 케이스 수, A, B는 문자열 길이)
공간: O(A + B)

문제