[완전탐색-1주][백준] 1062_가르침 [골4]

삽질log

본론만 말하는 글이 아니라, 그냥 제 삽질 과정을 기록합니다...

 

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

 

-----

 

1차 시도(틀림)

나의 사고 흐름은 무엇이었는가

 

• 일단 원문 그대로 입력받기
• anta와 tica 쳐내기
• 쳐낸 후 남은 것에서 a,c,i,n,t가 있으면 제거
• 남은 원소가 적은 순으로 sort(아마 이거 시간 복잡도 면에서 개쓰레기 같은 선택일듯)
• 결과 출력을 위한 세팅
  • result_list = 배울 알파벳을 담는 배열
  • rest_alpha = 이미 배운 알파벳을 제외하고, 남아있는 배울 수 있는 알파벳 수
  • result = 읽을 수 있는 단어의 수
• for문 내부 구조(2중 for문인 점에서 구리다고 볼 수 있다)
  • word_list = 현재 단어에서 이 단어를 읽기 위해 '새롭게' 배워야 할 단어
  • word_len = 이 단어를 읽기 위해 배워야 할 총 글자 수
  • word_comp = 이 단어를 읽기 위해 필요한 모든 글자를 탐색했는지 알아보기 위한 비교 변수
  • 이 단어를 완전히 읽기 위해 배워야 할 단어만 남아있음
    • 현재 글자가 result_list에 이미 있으면 word_comp+1
    • 현재 글자 result_list에 없으면서, 아직 rest_alpha가 0보다 크면, word_comp+1, word_list에 추가
    • 이 단어 내부 글자를 모두 탐색했을 때 word_len=word_comp면 이 단어는 읽을 수 있는 단어임, result+1
• result 최종 출력

근데 틀렸음...

import sys

n, k = map(int, input().split())

arr = [[list(str(input()))] for _ in range(n)]

if k < 5:
    print(0)
    sys.exit()

# arr에서 앞부분 alpha, 뒷부분 tica 제외

for i in range(n):
    arr[i] = arr[i][0][4:-4]

must = ['a', 'c', 'i', 'n', 't']

# a, c, i, n, t에 해당하면 삭제
arr_edit = [[] for _ in range(n)]
for i in range(n):
    for j in range(len(arr[i])):
        if arr[i][j] not in must and arr[i][j] not in arr_edit[i]:
            arr_edit[i].append(arr[i][j])

#arr_edit 원소 개수 적은 순으로 sort
arr_edit.sort(key = lambda x: len(x))

result_list = []
rest_alpha = k - 5
result=0

for i in range(n):
    word_len = len(arr_edit[i])
    word_comp = 0
    word_list = []
    for j in arr_edit[i]:
        # print(j)
        if j in result_list:
            word_comp+=1
        elif j not in result_list and rest_alpha>0:
            word_comp+=1
            word_list.append(j)
    if word_len == word_comp:
        result_list+=word_list
        rest_alpha-=word_len
        result+=1
# print(result_list)
print(result)

 

2차 시도(맞았음)

GPT 선생에게 뚜맞 당하면서 고쳐보자

 

• 애초에 입력 받을 때부터 앞 4글자, 뒤 4글자를 제거하고 받는다(스텝 감소) input()[4:-4]
• gpt는 list보다 set을 잘 쓰는 것 같다.
• 5개의 글자는 무조건 배워야 한다. k가 5보다 작으면 바로 0을 출력하고 시스템을 종료하자
• 필수로 배워야 하는 문자를 list가 아니라 set으로 선언한다 must = set('antic')
• 각 단어에서 must에 속하지 않는 문자들을 저장하자 unique_chars = set()
  • for문 내부 설명
    • remaining = 현재 단어 set(word)에서 필수 문자 must를 뺀다
    • arr_edit은 각 단어에서 must에 속하지 않는 문자를 저장하므로, remaining을 append하자
    • unique_chars는 총 단어를 합쳐서 새로 배워야 할 문자를 저장한다, remaining을 update한다(이미 있으면 추가 안됨)
• 문자를 배울 수 있는 남은 개수 rest_alpha = k-5
• 만약 더 배워야 할 문자가 없다면 unique_chars의 길이가 0임. 이 경우 모든 문자를 읽을 수 있음
  • n을 그대로 프린트하고 시스템을 종료하자
• gpt는 combination을 사용하라고 했다(근데 아마 시간복잡도 때문에 실전 코테에선 잘 안쓰는 방법일수도)
  • unique_chars와 rest_alpha로 combination을 만든다: 모든 남은 알파벳 중 rest_alpha 개수만큼 선택하는 조합 - comb_set
    • arr_edit에서 각 단어를 읽기 위해 배워야 하는 문자를 살펴본다
      • 문자들이 모두 comb_set에 들어있다면 읽을 수 있음. count+1
  • 위 조합에서 모든 경우를 헤아리면서, 가장 단어를 많이 있을 수 있는 경우를 max로 판별한다
• max_count값을 출력한다

맞았습니다로 뜸

import sys
from itertools import combinations

n, k = map(int, input().split())

# 입력받을 때부터 anta, tica 제외
words = [input()[4:-4] for _ in range(n)]

# 5개의 글자는 무조건 배워야 함, 5보다 작으면 어떤 단어도 배울 수 없음
if k < 5:
    print(0)
    sys.exit()

# 필수로 배워야 하는 문자들
must = set('antic')

# 각 단어에서 'antic'에 속하지 않는 문자들을 저장
unique_chars = set()
arr_edit = []

for word in words:
    # 'antic'에 속하지 않는 문자들만 남긴다
    remaining = set(word) - must
    arr_edit.append(remaining)
    unique_chars.update(remaining)

# 남은 알파벳을 배울 수 있는 개수
rest_alpha = k - 5

# 만약 남은 알파벳이 0개이면, 이미 'antic'으로만 읽을 수 있는 단어를 세기
if rest_alpha >= len(unique_chars):
    print(n)
    sys.exit()

# 가능한 조합 중 가장 많은 단어를 읽을 수 있는 조합을 찾음
max_count = 0

# 모든 남은 알파벳 중 rest_alpha 개수만큼 선택하는 조합을 만든다
for comb in combinations(unique_chars, rest_alpha):
    comb_set = set(comb)
    count = 0
    for remaining in arr_edit:
        # 남은 문자들이 모두 comb_set에 포함되어 있으면 단어를 읽을 수 있음
        if remaining <= comb_set:
            count += 1
    max_count = max(max_count, count)

# 결과 출력
print(max_count)

 

list만 습관적으로 쓰는데 set을 쓰는 방법을 좀 배워야할 듯.