[BOJ/백준 / Silver 5] 1181 : 단어 정렬 - Python

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

 

처음에 풀었던 풀이 -> 시간 초과가 났다

def sort_word() :
    word = []
    word_dict = {}
    answer = []
    len_max = 0

    # 단어 N개 입력받기
    N = int(input())
    for i in range(N) :
        word.append(str(input()))
    # print(word)

    # 중복된 단어 제거
    word = list(set(word))
    # print("set : ", word)
 
    # 1. 길이가 짧은 것부터 정렬
    # 키: 단어, 값: 단어 길이 -> dictionary 생성
    N = len(word)
    for i in range(N) :
        word_dict[word[i]] = len(word[i])
    # print(word_dict)

    # 단어 길이(value값)별로 정렬
    word_dict = list(sorted(word_dict.items(), key= lambda x: x[1]))
    # print(word_dict)

    # 2. 길이가 같으면 사전 순으로 정렬
    # 같은 길이의 단어가 몇 개인지 체크 -> 가장 긴 단어의 길이만큼 0값을 가진 리스트 생성
    # index: 단어 길이, 값: 같은 길이의 단어 개수
    len_max = word_dict[-1][1]
    # print(f"len_max: {len_max}")

    len_count_list = [0 for _ in range(len_max)]
    # print(len_count_list)

    word = []
    for i in range(N) :
        word.append(word_dict[i][0])
        index = word_dict[i][1] - 1
        len_count_list[index] += 1
    # print(word)
    # print(len_count_list)
    
    
    start_index = 0
    next_index = 0
    for i in range(len(len_count_list)) :
        if len_count_list[i] == 0 :
            pass
        elif len_count_list[i] == 1 :
            answer.append(word[start_index])
            start_index += 1
        elif len_count_list[i] > 1 :
            next_index = start_index + len_count_list[i]
            temp = word[start_index : next_index]
            # print(f"temp::: {temp}")
            for _ in range(len_count_list[i] - 1) :
                for j in range(len_count_list[i] -1) :
                    if (temp[j] > temp[j+1]) == True :
                        temp[j], temp[j+1] = temp[j+1], temp[j]
                    # print(f"temp : {temp}")
            answer[start_index : next_index] = temp[:]
            start_index = next_index
        # print(f"i: {i}, answer : {answer}, start_index: {start_index}")
    for word in answer :
        print(word)

    return ;

sort_word()

 

두번째 풀이 -> 시간초과는 안났지만 더 쉽게 푸는 방법에 대해 고민해야 했다.

def sort_word() :
    word = []
    answer = []
    len_max = 0

    # 단어 N개 입력받기
    N = int(input())
    for i in range(N) :
        word.append(str(input()))
    # print(word)

    # 중복된 단어 제거
    word = list(set(word))
    # print("set : ", word)
 
    # 1. 길이가 짧은 것부터 정렬
    # 키: 단어, 값: 단어 길이 -> dictionary 생성
    N = len(word)
    word.sort(key=len)
    # print(word)

    # 2. 길이가 같으면 사전 순으로 정렬
    # 같은 길이의 단어가 몇 개인지 체크 -> 가장 긴 단어의 길이만큼 0값을 가진 리스트 생성
    # index: 단어 길이, 값: 같은 길이의 단어 개수
    len_max = len(word[-1])
    # print(f"len_max: {len_max}")

    len_list = [0 for _ in range(len_max)]
    # print(len_list)

    for i in range(N) :
        index = len(word[i]) -1
        len_list[index] += 1
    # print(len_list)

    # 길이가 같은 단어들을 슬라이싱해서 정렬 후 새 리스트에 담기
    start_index = 0
    next_index = 0
    for i in range(len(len_list)) :
        if len_list[i] == 0 :
            pass
        elif len_list[i] == 1 :
            answer.append(word[start_index])
            start_index += 1
        elif len_list[i] > 1 :
            next_index = start_index + len_list[i]
            temp = word[start_index : next_index]
            # print(f"temp: {temp}")
            temp.sort()
            # print(f"sorted_temp : {temp}")
            answer[start_index : next_index] = temp[:]
            start_index = next_index
        # print(f"i: {i}, answer : {answer}, start_index: {start_index}")'''

    # 출력
    for word in answer :
        print(word)

    return ;

sort_word()

def sort_word() :
    word = []

    # 단어 N개 입력받기
    N = int(input())
    for i in range(N) :
        word.append(str(input()))

    # 중복된 단어 제거
    word = list(set(word))
 
    # 1. 길이가 짧은 것부터 정렬
    # 2. 길이가 같으면 사전 순으로
    N = len(word)
    word.sort(key= lambda x: (len(x), x))

    # 출력
    for w in word :
        print(w)

    return ;

sort_word()

파이썬 내장함수인 sort() 를 실행할 때 key 에 여러 조건을 한 번에 대입할 수 있다는 것을 알게 되었다.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

그래서 조건 두 개를 모두 만족하는 정렬을 코드 한 줄로 해결할 수 있었다.

ㅠㅠ 이걸 몰라서 직접 구현했던 코드는 접은글에 있으니 기억하고 싶을 때 찾아 보자 ^^!