진료순서 정하기

https://school.programmers.co.kr/learn/courses/30/lessons/120835

프로그래머스

---

문제 설명
외과의사 머쓱이는 응급실에 온 환자의 응급도를 기준으로 진료 순서를 정하려고 합니다. 정수 배열 emergency가 매개변수로 주어질 때 응급도가 높은 순서대로 진료 순서를 정한 배열을 return하도록 solution 함수를 완성해주세요.

---

제한사항

• 중복된 원소는 없습니다.
• 1 ≤ emergency의 길이 ≤ 10
• 1 ≤ emergency의 원소 ≤ 100

---

입출력 예

emergency	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]

---

입출력 예 설명

입출력 예 #1

• emergency가 [3, 76, 24]이므로 응급도의 크기 순서대로 번호를 매긴 [3, 1, 2]를 return합니다.

입출력 예 #2

• emergency가 [1, 2, 3, 4, 5, 6, 7]이므로 응급도의 크기 순서대로 번호를 매긴 [7, 6, 5, 4, 3, 2, 1]를 return합니다.

입출력 예 #3

• emergency가 [30, 10, 23, 6, 100]이므로 응급도의 크기 순서대로 번호를 매긴 [2, 4, 3, 5, 1]를 return합니다.

---

 

응급도의 순서대로 순서를 매기는 문제입니다.

이런 문제를 봤을 때 생각나는 풀이법은 먼저 emergency 배열을 내림차순으로 정리한 다음, index 함수를 사용해서 인덱스를 구하는 방법입니다.

이 문제에서는 중복된 원소가 없을 뿐더러, 정렬만 하기 때문에 값이 없는 경우는 없습니다.

 

파이썬의 index 함수를 사용해서 문제를 풀어보겠습니다.

def solution(emergency):
    # emergency를 내림차순 정렬합니다.
    semergency = sorted(emergency, reverse=True)
    # emergency의 값 e를 semergency에서 몇 번째 인덱스에 위치한지 찾습니다.
    # 인덱스는 0부터 시작이므로, 1을 더해 순서로 변환합니다.
    answer = [semergency.index(e) + 1 for e in emergency]
    return answer

최적의 방법은 아닙니다. 인덱스가 순회하는 과정에서 O(n^2) 시간 복잡도를 소모하기 때문입니다.

시간 복잡도를 줄이려면 딕셔너리를 사용하면 됩니다.

def solution(emergency):
    semergency = sorted(enumerate(emergency), key=lambda x: x[1], reverse=True)
    rank_dict = {value: rank + 1 for rank, (index, value) in enumerate(semergency)}
    answer = [rank_dict[value] for value in emergency]
    return answer

딕셔너리를 사용한 코드는 위와 같습니다. 이 코드는 O(n) 시간 복잡도를 소모합니다.