[백준] [Python] #1062 가르침

https://www.acmicpc.net/problem/1062

1062번: 가르침

풀어보려고 보니, 이전에 실패를 했다가 해결 못했던 문제였다.

처음에는 아 파이썬이면 string처리 어렵지않지~이러고 얕보고 풀기 시작했는데,

과거의 내가 실패로 놔두었던 이유가 있었다.

 

1차 시도

1. alphabet 리스트를 만들어서

2. 주어진 단어를 순회하면서 각 알파벳이 몇번째 단어에서 등장하는지 확인

  2-1. 한 단어에서 중복해서 등장하는 것 처리가 필요할것 같았지만 그러면 시간복잡도가 n^3이 되기에 포기함..

3. 등장 횟수에 따라 alphabet리스트 정렬 및 등장하지 않았던 알파벳은 제외

4. 몇가지 추가적인 조건으로 k개가 있다면,,,

  4-1. 여러번 등장한 것부터 배운다

  4-2. 한 단어에 여러번 등장하는 건 우선순위를 높여야하는가 낮춰야하는가..

해보다가 이건 도저히 아닌 것같고 소스가 너무 더러워졌다.

접근 자체가 잘못되었다는 생각으로 갓글에게 문의했다.

2차 시도

from itertools import combinations
import sys
sys.stdin = open("input.txt", "r")

n,k = map(int, input().split()) #3 6
word_list = []
for _ in range(n):
    word_list.append(input())

#필수못배우면의미없
if k<5:
    print(0)
    exit(0)

pre = 'anta'
post = 'tica'
must_alph = ['a','n','t','i','c']
alph = [ 'b', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'o', 'p', 
        'q', 'r', 's', 'u', 'v', 'w', 'x', 'y', 'z']

#읽을 수 있는지
def readable(word, must_alph):
    flag = True
    word = word[len(pre):-len(post)]
    for w in word:
        if w not in must_alph:
            flag = False
            break
    return flag

#k-5내에서 모든 조합 구하기 -> alph에서 k-5개 고르기
cnt = 0
for c in combinations(alph,k-5):
    cnt_new = 0
    for word in word_list:
        if readable(word,must_alph+list(c)):
            cnt_new += 1
    cnt = max(cnt,cnt_new)
print(cnt)

1. 필수로 배워야하는 알파벳에 대한 처리를 먼저 함

  1-1. k가 필수인 5개 미만이면 그 어떤 단어도 읽을 수 없으니 exit(0)

  1-2. must_alph에 필수 알파벳 넣어둠

2. 모든 조합 가능한 경우의 수를 combinations로 찾아내서

3. 언제 가장 많은 cnt가 걸리는지 확인한다.

이 문제로 가장 많은 사람들이 겪는 문제인 시간초과에 해당된 답안이다.

3차 시도

코드는 위와 같다.

다만,  언어를 pypy3로 선택하고 input을 받아오는 부분을 input()에서 sys.stdin.readline()로 변경하니 시간 안에 들어왔다.

from itertools import combinations
import sys

n,k = map(int, sys.stdin.readline().split()) #3 6
word_list = []
for _ in range(n):
    word_list.append(sys.stdin.readline())

#필수못배우면의미없
if k<5:
    print(0)
    exit(0)

pre = 'anta'
post = 'tica'
must_alph = ['a','n','t','i','c']
alph = [ 'b', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'o', 'p', 
        'q', 'r', 's', 'u', 'v', 'w', 'x', 'y', 'z']

#읽을 수 있는지
def readable(word, must_alph):
    flag = True
    word = word[len(pre):-len(post)]
    for w in word:
        if w not in must_alph:
            flag = False
            break
    return flag

#k-5내에서 모든 조합 구하기 -> alph에서 k-5개 고르기
cnt = 0
for c in combinations(alph,k-5):
    cnt_new = 0
    for word in word_list:
        if readable(word,must_alph+list(c)):
            cnt_new += 1
    cnt = max(cnt,cnt_new)
print(cnt)

---

참고

https://2hs-rti.tistory.com/m/11