백준 알고리즘: 1181번 단어 정렬 (Python)

문제 정보

---

1181번: 단어 정렬

 

 

핵심

---

1. 해당 단어들은 중복을 허용하지 않음

2. 길이가 짧은것부터 정렬하고, 길이가 같다면 사전순으로 정렬해야 함

 

풀이

---

나의 첫번째 풀이

import sys
def sol():
    n = int(input())

    words = [set() for _ in range(50)]
    for _ in range(n):
        l = input()
        words[len(l)-1].add(l)

    for w in words:
        if w:
            for w in sorted(list(w)):
                print(w)

sol()

 

 

핵심 1을 만족시키기 위하여 set 자료형을 문자열의 길이만큼 배열로 선언해두고,

핵심 2를 만족시키기 위하여 문자열의 길이에 따라 해당 배열에 집어넣었다

이후 문자열의 길이 순서에 따라서 출력하고, 집합을 리스트로 변환하고 정렬한 후 출력하였다

 

---

나의 두번째 풀이

import sys
def sol():
    _ = sys.stdin.readline()
    i = sys.stdin.read().split()

    for w in sorted(sorted(list(set(i))), key=len):
        print(w)

sol()

풀고나서 보니 다른 분들의 실행시간은 나보다 현저히 적었고, 더 효율적인 코드를 작성하기 위하여 공부를 하였다

보아하니, 파이썬의 sorted() 에는 key= 를 지정할 수 있는데 여기에 key=len 을 사용하면 문자열의 길이를 가지고 정렬해주는 기능이었다

따라서 해당 배열을 집합에 넣어서 중복을 제거 -> 첫번째 sorted() 로 문자열을 비교하여 사전순 정렬하고 -> 두번째 sorted(key=len)으로 문자열의 길이에 따라 정렬하면 핵심 1, 2를 만족하는 배열이 되는 것이다

 

 

고찰

---

다음과 같이 코드의 실행시간이 약 1/10배 줄어듦을 알 수 있었다

요인이라고 하면, 쓸데없는 공간을 만드는 과정  words = [set() for _ in range(50)]

한번에 한라인씩만 받는데에 소요되는 시간과 이를 하나하나 추가시키는 작업과

전체적으로 정렬시키지 않고, 문자열의 길이만 보고 따로따로 정렬시키는데 오는 오버헤드가 영향이 있지 않았나 싶다

새로운 지식인 sorted(key=len) 으로 다른 문제를 푸는데에 있어서 훨씬 효율적으로 풀이가 가능할 것 같다

 

참조

---

GitHub - dduneon/CodingTestPy

깃허브의 10번 prob을 참조하면 해당 문제의 첫번째 풀이와 두번째 풀이의 소스코드를 확인할 수 있다