1181번: 단어 정렬 [Python]

백준 알고리즘의 1181번 문제이다.

1. 일단 되게는 하자

num = int(input())
words = [[0]]

for i in range(num):
    a = 2
    tmpword = input()

    for j in range(len(words)):
        if tmpword in words[j]:     # 중복 방지
            a = 1
            continue
        if len(tmpword) == words[j][0]:     # 기존의 리스트에 입력 받은 단어 길이에 해당하는 숫자가 존재하면
            words[j].append(tmpword)
            a = 0

    if a == 1:      # 중복 방지
        continue
    elif a == 2:
        words.append([len(tmpword), tmpword])

words.sort()

for i in range(1, len(words)):
    words[i].remove(words[i][0])
    words[i].sort()
    for j in range(len(words[i])):
        print(words[i][j])

이 문제는 두 번의 정렬이 필요하다. 첫 번째는 알파벳 개수에 따른 정렬, 두 번째는 길이가 같은 경우 사전 순 정렬이다.

데이터 입력, 리스트 생성
carrot이라는 단어를 입력 받으면, [6, carrot] 으로 리스트에 추가한다. 여기서 6은 알파벳의 개수를 의미한다.
이 방식을 이용하여, 순차적으로 carrot, apple, blueberry를 입력하면, [[6, carrot], [5, apple], [9, blueberry]] 로 저장한다. 하지만 여기서 tomato를 입력하려고 할 때, tomato는 6글자이므로, carrot이 들어간 리스트에 추가해야 한다. 그러므로 [[6, carrot, tomato], [5, apple], [9, blueberry]] 가 되고, 리스트 추가에는 글자 수 존재 유무에 따라 두 가지 경우가 존재하는 것을 알 수 있다.

알파벳 개수 정렬
위 리스트 [[6, carrot, tomato], [5, apple], [9, blueberry]] 에서 각 리스트의 0번째 인덱스를 비교하여 정렬한다. 파이썬에서 list.sort() 함수로 위 리스트를 정렬하면, [[5, apple], [6, carrot, tomato], [9, blueberry]] 로 정렬이 된다.

사전 순 정렬, 출력
반복문으로 출력할 때, [6, carrot, tomato] 에서 숫자 6을 제거하고, 정렬을 한 뒤, 순서대로 출력한다.