[python_파이썬]백준_1181번_단어 정렬_풀이

공부하는허딩크 : https://www.youtube.com/live/MRweSf80fmw?feature=shared

한참을 고민했음.

조건이 2가지 (길이가 짧은 것부터, 길이가 같으면 사전순으로)

 

<첫번째 시도 : 시간초과>

import sys

input = sys.stdin.readline

N = int(input())

A = []

for _ in range(N):

    temp = input().strip()

    if temp in A:

        continue

    else:

        A.append(temp)

for i in range(len(A)):

    for j in range(len(A) - i -1):

        if len(A[j]) > len(A[j + 1]):

            A[j], A[j + 1] = A[j + 1], A[j]

for i in range(len(A)):

        for j in range(len(A) - i - 1):

            if len(A[j]) == len(A[j + 1]):

                if A[j] > A[j + 1]:

                    A[j], A[j + 1] = A[j + 1], A[j]

for i in A:

    print(i)

 

다시 봐도 조금 복잡하다.

버블정렬에서 사용하는 이중for문을 사용해서 2가지 조건을 하나씩 비교해 가면서 자리를 변경해 줬다.

정렬 정리 : https://heodinkcodingdiary.tistory.com/31

[python_파이썬] 정렬의 종류 (선택정렬, 삽입정렬, 퀵정렬, 병합정렬, 힙정렬, 기수정렬, 계수정렬)

 

일단 이게 시간 초과라는 것은 다른 시간복잡도가 빠른 정렬을 사용하면 괜찮다는거네?

 

어떤 정렬알고리즘을 사용할지 고민해보자. => 각 조건을 만족하는 이중for문을 2번 사용했으니 이걸 1번으로 줄여보자.

 

<두번째 시도 : 시간초과>

import sys

input = sys.stdin.readline

N = int(input())

A = []

for _ in range(N):

    temp = input().strip()

    if temp in A:

        continue

    else:

        A.append(temp)

for i in range(len(A)):

    for j in range(len(A) - i - 1):

        if len(A[j]) > len(A[j + 1]):

            A[j], A[j + 1] = A[j + 1], A [j]

        elif len(A[j]) == len(A[j + 1]):

            if A[j] > A[j + 1]:

                A[j], A[j + 1] = A[j + 1], A[j]

for i in A:

    print(i)

 

역시나 시간복잡도를 고려해서 다른 정렬 알고리즘을 사용해야 겠다.

중간에 for문의 조건을 약간만 수정하는걸 고민해보자.

 

<세번째 시도 : 시간초과 : for문 안에 약간만 수정>

for i in range(len(A)):

    for j in range(len(A) - i - 1):

        if len(A[j]) > len(A[j + 1]):

            A[j], A[j + 1] = A[j + 1], A [j]

        elif len(A[j]) == len(A[j + 1]) and A[j] > A[j + 1]:

            A[j], A[j + 1] = A[j + 1], A[j]

 

해당 정렬 알고리즘 (버블정렬, O(N^2))는 버려야 겠다.

이거 말고 계수정렬로 하려는데 도저히 답이 나오지 않는다. => 다른 사람들 풀이를 확인해보자.

어? sort가 중복이 가능하네?

 

<네번째 시도 : 맞았습니다. 다른 사람 풀이 참조>

import sys

input = sys.stdin.readline

N = int(input())

A = []

for _ in range(N):

    temp = input().strip()

    if temp in A:

        continue

    else:

        A.append(temp)

A.sort()

A.sort(key=len)

for i in A:

    print(i)

 

sort()만 하면 문자자체를 비교해서 알파벳순으로 비교가 된다.

sort(key=len)을 하면 len자리에 함수를 넣을 수 있는데 이렇게 하면 길이순으로 재배치 된다.

 

다른 풀이는 나처럼 continue를 하지 않고 그냥 단순히 입력값을 받은 수 set으로 중복 값을 제거 한후 새로운 변수에 저장했다.

 

의문점 : 길이순으로 재배치 되면 다시 알파벳순으로 비교가 풀리는거 아닌가?

   ㄴ일 단 알파벳순으로 재배치 된 후 그 안에서 다시 길이 순으로 배치가 되니까 가능함