코드코도

[2021 ICPC Sinchon Winter] [Python] 20920. 영단어 암기는 괴로워 - SILVER ⅲ 본문

Boj/Contest

[2021 ICPC Sinchon Winter] [Python] 20920. 영단어 암기는 괴로워 - SILVER ⅲ

고도고도 고도고도 2021. 5. 6. 13:22
728x90

본 게시글은 PC버전에 최적화 되어있습니다.

 

www.acmicpc.net/problem/20920

 

20920번: 영단어 암기는 괴로워

첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단

www.acmicpc.net

 

입력

첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. (1≤N≤100000, 1≤M≤10)

둘째 줄부터 N+1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10을 넘지 않는다.

단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.

 

출력

화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.

 

해결 방법

이 문제를 처음 풀었을 때 시간초과가 나왔다.

dict형을 사용해서 단어 빈도 수, 단어 길이, 사전 순을 key 값으로 정렬하는 방식으로 진행했는데 시간초과가 나왔다.

import sys

def main():
    words = dict()
    word_list = []
    n, m = map(int, input().split())
    for i in range(n):
        word = sys.stdin.readline().rstrip()
        if len(word) >= m:
            if word not in word_list:
                words[word] = [-1, -len(word), word]
                word_list.append(word)
            else:
                words[word][0] -= 1

    ans = sorted(words.items(), key = lambda x : (x[1][0], x[1][1], x[1][2]))

    for i in range(len(ans)):
        print(ans[i][0])

if __name__ == "__main__":
    main()

문제는 "if word not in word_list" 부분이였다.

처음 나온 단어인 경우 "words[word] = [-words[word] = [-1, -len(word), word]"와 같이 초기화를 해줄 필요가 있기에 word_list에 이미 입력된 단어인지 확인하는 과정을 거쳤다.

하지만 이 과정에서 추가적인 시간복잡도가 발생해서 시간초과가 나왔었다.

 

방법을 찾던 도중 파이썬 dict형에서 지원하는 get() 함수를 찾아냈고 위의 코드와 같은 역할을 수행한다는 것을 알아냈다.

심지어 dict형이므로 훨씬 시간복잡도가 줄어들었다.

 

아래가 수정한 코드이다.

import sys

def main():
    words = dict()
    n, m = map(int, input().split())

    for i in range(n):
        word = sys.stdin.readline().rstrip()
        if len(word) >= m:
            if words.get(word) is None:
                words[word] = [-1, -len(word), word]
            else:
                words[word][0] -= 1

    ans = sorted(words.items(), key = lambda x : (x[1][0], x[1][1], x[1][2]))

    for i in range(len(ans)):
        print(ans[i][0])

if __name__ == "__main__":
    main()

"if words.get(word) is None"으로 key의 value의 존재여부를 확인하고

None인 경우 초기화, 이미 입력된 단어인 경우 길이를 -1해준다.

 

value로 넣어준 값에 대한 설명을 해보자면,

첫번째 원소는 빈도 수, 첫 등장이면 -1 이후에도 계속 등장하면 -1을 해준다.

1을 빼주는 이유는 가장 많이 등장한 것을 제일 앞에 존재하도록 정렬하기 위해서이다. (정렬의 default는 오름차순)

물론 reverse = True를 사용해줘도 된다. 

 

두번째 원소는 단어의 길이, 이것 역시 가장 긴 것을 제일 앞에 존재하도록 정렬하기 위해 -부호를 붙여주었다.

 

세번째 원소는 단어 자체, 사전 순으로 정렬하기 위해 그대로 넣어줬다.

 

Python, Pypy 모두 통과

 

아무튼 코드를 수정해주니 통과되었다.

 

파이썬에 대해서 어느정도 자신이 있었는데 get()에 대해서는 처음 알았다.

지금까지 dict형을 쓸 때 시간 초과가 난 코드처럼 사용했었는데 dict형의 장점을 살리지 못했었다고 봐도 무방하다...

 

공부 열심히 해야겠다...

728x90
0 Comments
댓글쓰기 폼