Baekjoon Training #1062

---

#1062 가르침

오답(by chatGPT)

import itertools
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
words = [input().strip() for _ in range(N)]

if K < 5:
    print(0)
else:
    alpha_list = set('abcdefghijklmnopqrstuvwxyz') - set('antic')
    max_count = 0
    for comb in itertools.combinations(alpha_list, K-5):
        count = sum(all(c in comb for c in w[4:-4]) for w in words)
        max_count = max(max_count, count)
    print(max_count)

문제를 푸는 과정에서 코드가 너무 난잡해지고 시간초과도 지속적으로 떠서 chatGPT에게 코드 간결화를 요청하였더니 gpt가 짜준 정말 놀라운 코드이다. Python 라이브러리 활용을 극대화한 정말 간결한 코드이다. Python의 위력을 다시한번 느꼈다. 그러나 이 코드는 "a,n,t,i,c"은 무조건 반영되어야 하고 해당사항을 고려하여 양쪽 네개씩을 제외한 문자들을 체크해야한다는 점을 고려하지 않아서 틀린코드이다. 그럼에도 참고할만한 사항이 존재하는 코드이기에 첨부하였다.

특히 count = sum(all(c in comb for c in w[4:-4]) for w in words)이 라인이 재밌었다. count += a 방식을 사용하지 않고 sum을 이용한 것도 특이했고 all이라는 함수를 이용하여 comb와 w[]에 동시에 존재할때 1을 출력하는 방식도 신기했다.

---

pypy3가 반복적인 코드에서 시간적인면에서 우위가 있기에 pypy3로 코드를 제출하였다.

 

import sys
input = sys.stdin.readline  # 시간단축 코드

N, K = map(int, input().split())    # 단어수를 N으로 배우는 글자수를 K로 입력
words = []  # 단어 종류를 담아둘 리스트 생성
for _ in range(N):  # 단어 수 만큼 반복하여 리스트에 입력
    words.append(input().strip())

alpha = ['a', 'n', 't', 'i', 'c']   # 학습한 알바펫를 담아둘 리스트(a,n,t,i,c)는 필수로 학습
# a,n,t,i,c를 제외한 알파벳 리스트
alpha_list = ['b', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm',
              'o', 'p', 'q', 'r', 's', 'u', 'v', 'w', 'x', 'y', 'z']
result = 0

# check function 정의
def check():
    cnt = 0     # cnt를 0으로 초기화
    for w_check in words:   # words리스트 전부 체크
        readable = 1    # 읽을 수 있는 단어임을 확인하는 변수를 1(읽을 수 있음)으로 초기화
        for i in range(4, len(w_check)-4):  # 단어의 문자를 전,후반 4개씩 제외하고 체크
            if w_check[i] not in alpha:     # alpha에 포함되지 않으면
                readable = 0                # 읽을 수 없다고 판단
                break
        if readable == 1:   # 읽을 수 있다면
            cnt += 1        # 카운팅
    return cnt      # check함수의 출력은 cnt

# choose_alpha function 정의
def choose_alpha(n, start):     # 배운 문자수에 따라 알파벳 조합을 연산하는 함수
    global result
    if n == 0:      # n=0 즉 checking이 종료되면   
        result = max(result, check())   # result를 기존의 result와 check함수의 결과인 cnt중 더 큰수로 교체
        return
    # 5개의 default 알파벳을 제외하고 남는 알파벳들의 조합 생성하여 alpha list로 옮겨주는 과정
    for i in range(start, len(alpha_list)):     
        alpha.append(alpha_list[i])
        choose_alpha(n-1, i+1)  # recursion
        alpha.pop()
# 학습한 알파벳이 5개 이하면 어떠한 단어도 읽을 수 없음
if K < 5:
    print(result)
# 무조건 학습할 알파벳 5개를 제외하고 첫번째 알파벳부터 선택하여 전수조사
else:
    choose_alpha(K-5, 0)    
    print(result)

주석으로 자세히 설명해놓았기에 전반적인 발상만 되집어보고 넘어가자.

우선 전반부 4개, 후반부 4개의 알파벳은 "a,n,t,i,c" 5가지 알파벳들로 구성이 되어있으므로 학습할 알파벳은 최소 5개이상이 되어야 단어를 하나라도 읽을 수 있다. 따라서 학습할 알파벳을 기본적으로 a,n,t,i,c를 잡아두고 학습하는 알파벳 숫자에 따라 해당 5개 이외의 알파벳을 알고 있는 알파벳에 추가해주어 몇개의 단어나 통과가 되는지 전수조사하여 그 최대값을 출력해주는 방식이다.

---