조건 처리를 잘 해주어야만 빠르게 정답을 맞출수 있는 문제인 것 같다. 계속 풀어보다 도저히 정답처리가 안나와서 다른 사람 풀이를 적극.. 참고하였다.
n개의 단어와 k(배울 수 있는 알파벳 개수)를 입력받고, 어떤 조합으로 k개의 알파벳을 익혀야 최대한 많이 단어를 읽을 수 있는지에 대한 문제이다. 참고로 단어는 무조건 'anta'로 시작해서 'tica'로 끝이 난다. 즉 단어의 형태는 anta[?]tica
이다
풀이 순서는 아래와 같다.
단어를 하나씩 입력 받는다. 단어는 중복 알파벳이 섞여있을 수 있으므로 집합으로 형변환을 하여 꼭 필요한 알파벳이 무엇인지 확인한다.
각 단어를 구성하는 unique한 알파벳 집합(curUnique)을 uniqeList에 담는다.
각 단어를 구성하는 unique한 알파벳 집합(curUnique)을 uniqueSet과 합집합을 만들어 update한다.
예외 조건들을 미리 처리한다
(1) required 글자는 단어 내에 필수로 들어가므로 최소 5개의 글자를 배워야 하는데 k 자체가 5 미만이라면 그 자리에서 cnt 출력 후 종료
(2) K는 5보다 크거나 같은데, len(uniqueList) == 0이라는 뜻은 주어진 words가 모두 a,n,t,i,c 5개 알파벳으로만 이루어진 경우 아래 과정 반복할 필요 없으므로 그 자리에서 cnt 출력 후 종료
(3) antic 외에 K-5개 이하로 알파벳을 사용해도 모든 단어를 다 읽을 수 있는 경우 아래 과정 반복할 필요 없으므로 그 자리에서 cnt 출력 후 종료
⭐️ 이제 a,n,t,i,c 를 제외한 단어 속 unique한 알파벳들(uniqueSet) 중 k-5개의 글자를 골라야한다. ⭐️ 이 때, 어떤 조합으로 골라야 가장 많은 단어를 읽을 수 있는지 combinations를 통해 brute-force 진행한다.
처음에 생각 할 때엔 단어의 길이가 짧은 것이 우선순위가 높다고 판단하여 uniqueList의 길이가 짧은 순으로 정렬하여 조합을 구했으나 이에 대한 반례가 있어, 완전 탐색으로 구해야 한다. (모든 알파벳 조합을 찾기 보단, uniqueSet 내에서만 조합을 찾아서 조금 더 효율적으로 brute-force 진행)
다양한 조합 경우의 수에 대하여, uniqueList의 요소에 하나씩 접근하여 현재 조합이 현재 uniqueList의 요소의 superset(상위집합) 인지 판단한다.
true라면 tmpAns에 1을 더한다. 이러한 방식으로 모든 조합 경우의 수에 대하여 tmpAns값을 구하고, maxCnt와 tmpAns의 최댓값을 구해나간다.
최종적으로 cnt += maxCnt하면 끝 !
from itertools import combinations
import sys
input = sys.stdin.readline
n, k = map(int, input().strip().split())
def solve(n, k):
required={'a','n','t','i','c'}
uniqueList=[]
# 빈 집합을 만들 때엔 {}대신 set()을 사용. {} 사용 시 딕셔너리가 생성됨 주의
uniqueSet=set()
cnt=0
for _ in range (n):
cur = input().strip()
curSet =set(cur)
curSetLen =len(curSet)
# print(curSetLen)s
# 절대 읽을 수 없는 경우는 아예 배제
if curSetLen > k:
continue
# 무조건 읽는 경우
if curSetLen == 5:
cnt += 1
continue
# 단어를 구성하는 unique한 글자(중복x) 뽑기 (set활용)
curUnique = curSet-required
uniqueList.append(curUnique)
# update와 unique 차이 잘 알고 쓸 것 (..)
uniqueSet.update(curUnique)
# required 글자는 단어 내에 필수로 들어가므로 최소 5개의 글자를 배워야 하는데 k 자체가 5 미만이라면 그 자리에서 종료
if k<5:
return 0
# K는 5보다 크거나 같은데, 주어진 words는 모두 a,n,t,i,c 5개 알파벳으로만 이루어진 경우 아래 과정 반복할 필요 없으므로 그 자리에서 종료
if len(uniqueList) == 0:
return cnt
# antic 외에 K-5개 이하로 알파벳을 사용해도 모든 단어를 다 읽을 수 있는 경우 아래 과정 반복할 필요 없으므로 그 자리에서 종료
if len(uniqueSet) <= k-5 :
print(1)
return cnt + len(uniqueList)
maxCnt=0
# {'a','n','t','i','c'}를 제외한 단어 속 unique한 글자들 중 k-5개의 글자를 고를 것임.
# 이 때, 어떤 조합으로 골라야 가장 많은 단어를 읽을 수 있는지 combinations를 통해 brute-force 진행
for c in combinations(uniqueSet,k-5):
caseSet = set(c)
tmpAns = 0
for uniqueWord in uniqueList:
if caseSet.issuperset(uniqueWord): # 또는 uniqueWord.issubset(caseSet)
tmpAns+=1
maxCnt=max(maxCnt,tmpAns)
cnt += maxCnt
return cnt
print(solve(n,k))