진료순서 정하기
2024. 7. 26. 18:00ㆍ코딩테스트 입문
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) 시간 복잡도를 소모합니다.