[Programmers][Python] 진료순서 정하기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/120835

프로그래머스

 

처음 작성한 코드

• emergency 리스트 요소의 숫자가 클 수록 진료순서의 오름차순의 순서를 받는다.
  • 딕셔너리로 리스트 요소를 key로, 순서를 value로 인덱싱을 한다.
  • 이때 큰 숫자가 낮은 값을 배정 받기 위해 순서값 i를 1부터 리스트의 길이까지 역순으로 인덱싱을 하였다.

• Sorted 함수를 이용하여 item들의 순서를 정렬한다.
  • Sorted 함수는 기본적으로 오름차순
  • 딕셔너리와 .items() 를 이용해주어야 key와 value 쌍이 key 순으로 정렬된다.

• 정렬된 딕셔너리 item들의 value 값들은 우리가 찾아내야할 진료 순서가 된다.

def solution(emergency):
    emergency_dict = {string: len(emergency) - i for i, string in enumerate(emergency)}
    emergency_dict_sorted = dict(sorted(emergency_dict.items()))
    return list(emergency_dict_sorted.values())

# 입출력 예시
print(solution([3, 76, 24]))
print(solution([1, 2, 3, 4, 5, 6, 7]))
print(solution([30, 10, 23, 6, 100]))

문제를 처음보고 마땅히 인덱싱을 할 방법이 딕셔너리 밖에 없었다고 생각했는데, 다른 코드와 비교하면서 생각보다 코드를 잘 만들었다고 생각된다.

 

다른 코드

[코드1]

• emergency 리스트 요소의 숫자를 내림차순으로 정리한다.
• 각 요소의 숫자가 내림차순으로 정리했을때 몇 번째 인지 확인한다.

def solution(emergency):
    e = sorted(emergency,reverse=True)
    return [e.index(i)+1 for i in emergency]

굉장히 직관적인 코드이지만 사용하기에는 좋지않다. N개의 요소가 있는 리스트에서 각 요소들을 서치하는 방법이기 때문이다. [코드1]은 이러한 방법 때문에 O(N^2)의 시간복잡도를 가지고, 처음 작성한 코드는 sorted 함수의 최대 시간복잡도인 O(NlogN)을 가지게 된다. 그리고 무엇보다 인덱싱을 할때는 한 쌍으로 묶어정리 할 수 있는게 좋지 않을까.