[파이썬] 백준 1501 영어읽기

백규현·2022년 5월 11일
0

문제에서 N,M의 범위가 10000 이다. 완전탐색을 한다고 하면 O(NM단어 및 문자의 길이) 이므로 절대 풀 수 없다.
그러므로 특수한 방식의 전처리를 해야하는데 단어의 길이가 가변적이므로 n차원 리스트에 저장하는 것 또한 쉽지않다.

문제에서 첫글자,마지막글자를 제외한 가운데 글자들은 순서가 상관이 없다고 한다.
그렇기 때문에 우리는 각각의 알파벳이 몇개 있는지만 신경쓰면 된다.
그러므로 나는 가운데 문자열을 정렬하여 표기해보았다.
예를 들어 예제입력의 사전에 있는 단어들을

{
	'aa': {
    		'abb': 2, 
            'abc': 1
          }
}

과 같이 표현할 수 있다.
ababa 와 aabba 는 모두 가운데 문자열을 정렬했을때 'abb' 형태이기 때문에 'abb':2 와 같은 형태로 개수를 표기한 것이다.

코드

import sys
from collections import defaultdict
input = sys.stdin.readline
dic = defaultdict(dict)
for _ in range(int(input())):
    line = input().strip()
    i = line[0]+line[-1] if len(line)>1 else line[0]
    k = ''.join(sorted(line[1:-1]))
    dic[i][k] = dic[i].get(k,0)+1
for _ in range(int(input())):
    ans = 1
    for line in input().strip().split():
        i = line[0]+line[-1] if len(line)>1 else line[0]
        k = ''.join(sorted(line[1:-1]))
        ans *= dic[i].get(k,0)
    print(ans)
  • 단어의 길이가 1일 경우와 2일 경우를 잘 구별해야한다.
    예를 들어 'aa' 와 'a' 라는 단어가 있다고 할때
aa : {
	'' : 2
	}

형태로 저장될 수 있기 때문이다. 그러므로
i = line[0]+line[-1] if len(line)>1 else line[0]
라인을 이용해 해결했다.

  • defaultdict를 사용할 줄 알면 조금 더 수월하게 문제를 풀 수 있다.
profile
반갑습니다.

0개의 댓글