[Python] 백준 1759. 암호만들기 (조합, 집합)

Concept

• 주어진 문자들 중에서 L개로 만들 수 있는 모든 조합을 구한다.
• 각 조합이 다음 두 가지 조건을 만족시키면, 그 조합을 오름차순으로 청렬하여 정답 list에 저장한다.
  1) 모음이 최소 한 개인지
  : 모음 집합과 교집합결과 집합 길이가 1 이상이면 만족
  2) 자음이 최소 2 개인지
  : 자음 집합과 교집합한 결과 집합 길이가 2 이상이면 만족
• 위 두 조건을 만족시킨 조합들을 오름차순으로 정렬하고, 차례로 각 조합을 출력

알게 된 점

• 집합들의 교집합, 합집합, 차집합의 시간 복잡도는 O(len(s) + len(t))
  
  

코드

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

if __name__ == '__main__':
     l, c = map(int, input().split())
     chars = list(input().strip().split())
     pwd = []
     vowels = {'a', 'e', 'i', 'o', 'u'}
     consonants = {'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v','w', 'x', 'y', 'z'}
     
     for comb in combinations(chars, l):
          if set(comb).intersection(vowels):
               if len(set(comb).intersection(consonants)) >= 2:
                    pwd.append(sorted(comb))
     pwd.sort()
     for p in pwd:
          print(''.join(p))