[백준] 1062번: 가르침

한동안 TIL을 작성하지 못했다. 가장 주요한 요인으로는 몸이 아주 지쳐있었는지 번아웃이 왔다. 세무조사를 포함해 쉽지 않았던 직장생활을 마치고 곧장 정글에 뛰어들어 갈아 넣었으니, 용케 버틴 게 다행일 정도이다. 그러던 와중에 어떤 협력사에서 서류 접수 이틀만에 불합격 통보를 보내와서 맥이 빠졌다. 코딩테스트가 하도 어려워서 대부분 떨어진다고 하도 겁을 주길래, 최소한 코딩테스트는 볼 줄 알았다. 가고 싶은 회사 중 하나였고, TO가 많이 줄어들었다고 했지만 지원을 철회하지 않았다. 하지만 회사 사정상 채용을 더 이상 진행하지 않겠다고 하니... 아쉬운 카드만 하나 날린 셈이다.

그래서 다음 날 비행기 티켓을 끊어서 제대로 리프레싱을 하고 왔다. 나 스스로가 마음이 불편해서 노트북을 챙겨가 하루에 알고리즘 문제 한두 개씩은 풀었지만, 최대한 휴식을 취했다. 돌이켜보니 코로나와 함께 취업 준비, 일, 공부로 쉴 틈 없이 달려온 지난 3년이었다. 고작 2박 3일 다녀온 여행이었지만, 제대로 리프레싱하고 왔으니 다시 달릴 일만 남았다.

다시 시작하는 김에, 오늘부턴 날짜로 작성하는 TIL이 아니라, 공부한 내용을 바탕으로 작성하는 개발일지로 갈아타려고 한다 :)

알고리즘

백준 - 가르침 풀이

오늘은 4개의 알고리즘 문제를 풀어보았다. 그 중에 가장 어려웠던 문제에 대한 개발일지를 작성해보고자 한다. 바로 가르침 이라는 문제였다.

문제를 보고는 아주 쉽다고 생각했는데, 상당히 시간이 오래 걸렸다.
조건을 이것저것 걸어주어야 해서 그런 것이었는데....

우선 문제를 보면, 주어지는 N개의 단어를 각각 몇 개의 알파벳으로 읽을 수 있는지를 파악해야 한다.

def sol(n,k):
	uniqueList = []
    uniqueSet = set()
	cnt = 0
 
	for _ in range(n):
		now = input().strip() # 주어진 현재 단어
		nowset = set(now)     # 주어진 현재 단어를 구성하는 알파벳의 집합
		nowcnt = len(nowset)  # 주어진 현재 단어를 구성하는 알파벳의 갯수

그리고, 어떤 단어를 읽는데 필요한 알파벳 수가 K보다 크다면 당연히 그 단어는 K개의 알파벳만 가르쳐서는 읽을 수 없을 것이다. 한편 그 갯수가 만약 5라면, 딱 antic만 사용해서 읽을 수 있는 단어이므로 무조건 읽을 수 있을 것이다.

# 읽을 수 없는 경우
if nowcnt > k:
	continue
# 무조건 읽는 경우
if nowcnt == 5:
	cnt += 1
	continue

지금까지 걸러내지 못한 케이스는, 현재 단어를 읽는데 필요한 알파벳이 5개보다는 많고 K 이하인, antic외에 추가적으로 K-5개가 필요한 경우이다. 바로 이 경우들에 대해서, 추가적으로 K-5개만큼의 어떤 알파벳을 고를 때 가장 많은 단어를 읽을 수 있을지를 추후에 검증해주어야 한다. 따라서 별개의 리스트인 uniqueList에 넣어주도록 하자.

또한, antic 외에 지금까지 어떤 알파벳들을 추가적으로 필요로 했는지를 uniqueSet에 업데이트 해주자. uniqueSet을 활용하면 추가할 알파벳 후보를 소문자 26개에서 antic을 제외한 21개 전체로 할 필요가 없고, uniqueSet에 포함되어 있는 알파벳만 포함시킬 수 있기 때문이다.

# 6개 이상 K개 이하인 경우
nowunique = nowset - {'a','n','t','i','c'}
uniqueList.append(nowunique)
uniqueSet = uniqueSet.union(nowunique)

여기까지 주어진 N개의 단어를 모두 일단 받으면서 처리를 했으면, 이제는 굳이 갯수를 확인할 필요가 없는 것들에 대한 사전처리를 해줄 시간이다.

우선 '모든 단어는 "anta"로 시작되고, "tica"로 끝난다'는 문제 조건에 따라서, 남극언어의 가장 짧은 단어는 8자리 글자인 antatica 이다. 그리고 그 antatica을 읽으려면 총 5개의 알파벳(a,n,t,i,c)을 가르쳐야 한다. 따라서, K가 5보다 작은 숫자로 주어진다면 정답은 0이 되어야 한다.

# K가 5보다 작으면, 단 하나의 단어도 읽을 수 없음
if k < 5:
	return 0 

또한 K가 5보다 같거나 크더라도, N개의 단어가 모두 antic 을 가지고 읽을 수 있었거나 아예 K보다 많은 알파벳을 필요로 했던 경우도 발생할 수 있다. 이런 경우엔 N개의 단어를 읽어들이는 for문에서 단 한 번도 uniqueList에 추가가 발생하지 않는다. 따라서 for문에서 antic을 가지고 읽을 수 있었던 갯수만큼의 단어들을 읽을 수 있는 셈이니 역시나 바로 처리해준다.

# K는 5보다 크거나 같은데, 주어진 words는 모두 a,n,t,i,c 5개 알파벳으로만 이루어진 경우
  if len(uniqueList) == 0:
    return cn

한편 uniqueSet에 들어있는 알파벳의 갯수가 K-5보다 작은 경우도 처리해줄 수 있다. 가령 uniqueSet에는 3개의 알파벳이 들어있고, K는 10이라고 가정해보자. 그럼 antic 외에 그 3개의 알파벳을 포함해서 총 5개를 추가적으로 가르치게 되면, uniqueList에 들어있는 단어들은 모두 읽을 수 있게 된다. K가 8이어도 마찬가지이다.

여기서 return을 N으로 해줘서 계속 에러가 났었다 ,,,

  # antic 외에 K-5개 이하로 알파벳을 사용해도 모든 단어를 다 읽을 수 있는 경우
  if len(uniqueSet) <= k-5 :
    return cnt + len(uniqueList)

여기까지 해서도 처리가 안된 경우는, uniqueList를 이제는 직접 들여다보며 uniqueSet에 있는 알파벳들 중에 K-5개를 어떤 조합으로 선택할지를 탐색해보아야 한다. 간단히 Python에서 제공하는 itertools의 combinations를 활용하면, uniqueSet에서 k-5개만큼을 순서 상관없이 고르는 '조합'을 편리하게 구할 수 있다.

# K-5개의 알파벳을 어떤 조합으로 골라야 가장 많이 읽을 수 있나 Brute-Force
  maxCnt = 0
  
  for case in itertools.combinations(uniqueSet, k-5):
    caseCnt = 0
    caseSet = set(case)
    for candidateSet in uniqueList:
      if candidateSet.issubset(caseSet):
        caseCnt += 1
    maxCnt = max(maxCnt, caseCnt)

결국 문제를 잘 읽고 어떤 조건을 설정해줄지만 잘 선택하면 되는 문제인데, 15분만에 첫 코드를 제출했지만 이후에 수많은 시도를 통해 거의 2시간을 걸려 정답을 확인할 수 있었다. 정답률이 상당히 낮고, 공유 문제풀이 시트를 보니 정글에서도 푼 사람이 별로 없는 문제인거 같다. 중간에 포기할뻔 했으나, 끈질기게 이겨내고 풀어내서 뿌듯하다 😎

개인적으론 문제 제목을 정말 잘 지은 것 같다. 쉬워보이지만 상당히 까다로워서, 풀다보면 '조건 확인을 잘하자', '포기하지 않으면 길이 보인다'는 2가지 '가르침'을 주는 문제다.

이러한 과정을 통해서 작성한 전체 코드는 다음과 같다.

'가르침' 전체 코드

import sys
import itertools
# anta # tica 
# a n t i c 이 없으면, 한 단어도 읽을 수 없다.
# 최소 5개는 읽을 수 있어야 한다. 

input = sys.stdin.readline 
N, K = map(int, input().strip().split())

def sol(n, k):
  # 초기 셋팅
  uniqueList = []
  uniqueSet = set()
  cnt = 0
  # N개의 단어 읽기
  for _ in range(n):
    now = input().strip()
    nowset = set(now)
    nowcnt = len(nowset)
    # 읽을 수 없는 경우
    if nowcnt > k:
      continue
    # 무조건 읽는 경우
    if nowcnt == 5:
      cnt += 1
      continue
    # 6개 이상 K개 이하인 경우
    nowunique = nowset - {'a','n','t','i','c'}
    uniqueList.append(nowunique)
    uniqueSet = uniqueSet.union(nowunique)

  # 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 :
    return cnt + len(uniqueList)

  # K-5개의 알파벳을 어떤 조합으로 골라야 가장 많이 읽을 수 있나 Brute-Force
  maxCnt = 0
  
  for case in itertools.combinations(uniqueSet, k-5):
    caseCnt = 0
    caseSet = set(case)
    for candidateSet in uniqueList:
      if candidateSet.issubset(caseSet):
        caseCnt += 1
    maxCnt = max(maxCnt, caseCnt)

  # 최종적으로 얻어낸 cnt를 얻어서 반환해주기
    
  cnt += maxCnt
  return cnt
  
print(sol(N, K))