순서정하기

• 프로그래머스-진료순서정하기

주어진 배열에서 큰 숫자의 위치에 순서대로 숫자를 채워 출력합니다.

조건

• 중복된 원소 없음
• 1 <= 입력된 배열의 길이 <= 10
• 1 <= 입력된 배열의 원소 <= 100

예시

input	result
[3, 76, 24]	[3, 1, 2]
[1, 2, 3, 4, 5, 6, 7]	[7, 6, 5, 4, 3, 2, 1]
[30, 10, 23, 6, 100]	[2, 4, 3, 5, 1]

기존 작성 코드 및 문제

• 아래의 코드는 sorted에서 이미 O(NlogN) 정도의 시간이 든다고 가정합니다.
• 그리고 반복문에서 index를 계속 부르게 되므로 계속 부르게 되므로 O(N^2)의 시간복잡도를 가지게 됩니다.

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

문제 해결 코드 및 설명

• 이를 시간복잡도의 효율을 생각해서 dict을 사용하여 코드를 작성해봅니다.

def solution(emergency):
    dict_sorted = {e : i+1 for i,e in enumerate(sorted(emergency)[::-1])}
    return [dict_sorted[x] for x in emergency]

• 오름차순으로 정렬하는 것은 sorted 함수에 [::-1]로 표현해주었다.
  • sorted에 reverse = True 매개변수를 집어 넣어주어도 됩니다.
• {} 반복문을 List Comprehension 방법으로 표현합니다.
  • enumerate 를 사용하여 인덱스를 순서로 표현합니다.
  • 값을 순서대로 넣어주는 방법으로 진행합니다.
• 만들어진 dict 에서 배열 원소를 입력받아 해당 인덱스를 출력합니다.
• 이와 같은 방법으로 기존의 시간 복잡도보다 훨씬 줄어든 O(NlogN)의 모습으로 실행할 수 있습니다.