문제
풀이
조건 처리를 잘 해주어야만 빠르게 정답을 맞출수 있는 문제인 것 같다. 계속 풀어보다 도저히 정답처리가 안나와서 다른 사람 풀이를 적극.. 참고하였다.
n개의 단어와 k(배울 수 있는 알파벳 개수)를 입력받고, 어떤 조합으로 k개의 알파벳을 익혀야 최대한 많이 단어를 읽을 수 있는지에 대한 문제이다. 참고로 단어는 무조건 'anta'로 시작해서 'tica'로 끝이 난다. 즉 단어의 형태는 anta[?]tica 이다
풀이 순서는 아래와 같다.
-
단어를 하나씩 입력 받는다. 단어는 중복 알파벳이 섞여있을 수 있으므로 집합으로 형변환을 하여 꼭 필요한 알파벳이 무엇인지 확인한다.
- 이 때 현재 단어의 집합(=curSet)의 길이(=curSetLen)가 k보다 크다면 절대 읽을 수 없으므로 해당 단어는 무시한다.
- 현재 단어의 집합의 길이가 5라면 해당 단어는 무조건 읽을 수 있으므로 최종 결과값 변수인 cnt에 1을 더한다. (why? 문제 조건대로라면 단어는 anta로 시작해서 tica로 끝나므로 우리는 필수로 'a,n,t,i,c' 알파벳을 알아야 단어를 읽기 시작할 수 있다. 따라서 현재 단어의 집합의 길이가 5라면 'a,n,t,i,c' 로만 이루어진 단어임을 알 수 있다.)
-
각 단어를 구성하는 unique한 알파벳 집합(curUnique)을 uniqeList에 담는다.
- 여기서 unique한 알파벳 집합 이란 필수 알파벳인 'a,n,t,i,c'를 제외한 집합을 의미한다.
- uniqueList는 추후 단어를 읽을 수 있는 지 여부를 최종적으로 판단할 때 쓸 것이다.
-
각 단어를 구성하는 unique한 알파벳 집합(curUnique)을 uniqueSet과 합집합을 만들어 update한다.
- 각 단어는 독립적이므로 unique한 알파벳 집합을 생성하더라도 이들을 단순히 합하면 중복이 생길 수 있으므로 합집합을 구한다.
- uniqueSet은 추후 k-5개의 알파벳 조합을 구성하기 위해 combinations를 사용하게 되는데, 해당 메소드의 인자로 쓰게 될 것이다. (5번 참고)
-
예외 조건들을 미리 처리한다
(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))
🦾 깨달은 점
- 브루트 포스 방식을 쓰더라도 최대한 효율적으로 쓰려고 노력해보자
- set 자료형에 대해 다시 한 번 복습할 수 있었던 시간이었다
- set의 union()은 원본 갱신이 아니므로 변수에 다시 담아야함. 원본 갱신을 원한다면 update()사용
- issubset, issuperset
- 모든 코드를 실행하지 않아도 되는 입력의 경우 바로 조건처리로 return을 해줌으로써 최대한 compact하게 풀이할 수 있도록 노력해야겠다
