입문 - 진료 순서 정하기

입문 - 진료 순서 정하기

문제설명

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

---

제한사항

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

---

입출력 예

 

---

입출력 예 설명

입출력 예 #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 배열에 있는 두 요소 i,  j를 비교하여 i가 j보다 작다면 answer배열에 i 값에 1을 더해서 emergenct값이  가장 큰 수가 1을 얻고, 다음 큰 수가 2, 이런식으로 answer 배열이 새롭게 만들어진다.

>> 배열의 크기가 작다면 이중반복문을 해도 상관없지만, 배열의 크기가 크다면 이 방법은 시간이 너무 오래 걸린다.

class Solution {
    public int[] solution(int[] emergency) {
        int[] answer = new int[emergency.length];
        for (int i = 0; i < emergency.length; i++) {
            for (int j = 0; j < emergency.length; j++) {
                if (emergency[i] < emergency[j]) {
                    answer[i]++;
                }
            }
            answer[i]++;
        }
        return answer;
    }
}

---

개선된 풀이

>> emergency배열을 순서대로 정렬할 sortedEmergency 배열을 만들고 clone 메소드를 이용해 emergency 배열을 복제한다.

>> Arrays 클래스를 이용해 sort 메소드로 sortedEmergency 배열을 정렬해준다.(기본적으로 오름차순 정렬 : 1, 2, 3...)

>> 반복문을 이용해 정렬된 배열에 위치를 answer 배열에 입력한다.

>> binarySearch는 특정배열에 특정요소를 찾는데 사용된다. 여기서는 sortedEmergency 배열에서 emergency의 i번쨰 인덱스의 값을 찾을 수 있다. 

>> answer 배열의 i번째 인덱스 값은 배열의 길이에서 idx값을 빼준 값을 넣어주면 응급도를 알 수 있다.

 

>> 입출력 1을 예시를 들면 [3, 76, 24]를 sort로 정렬하면 [3, 24, 76]이 된다.

>> i가 1이라고 가정하면 emergency[1] = 76인데, 정렬된 배열에서는 2의 인덱스에 위치한다. idx는 2가 된다.

>> answer[1]에는 배열에 길이에서 idx에 뺀 값, 3 - 2 = 1, answer[1] = 1, 가장 응급도가 높다. 

import java.util.Arrays;

class Solution {
    public int[] solution(int[] emergency) {
        int[] answer = new int[emergency.length];
        int[] sortedEmergency = emergency.clone();
        Arrays.sort(sortedEmergency);

        for (int i = 0; i < emergency.length; i++) {
            int idx = Arrays.binarySearch(sortedEmergency, emergency[i]);
            answer[i] = emergency.length - idx;
        }
        return answer;
    }
}

---

알아보기

>> Arrays.binarySearch 메서드는 주어진 배열에서 이진 검색(이분 탐색)을 수행하여 특정 요소의 인덱스를 찾는데 사용된다.

>> binarySearch(T[] a, T key)

• a: 이진 검색을 수행할 배열(정렬)
• key: 찾고자 하는 요소
• 요소 key가 배열 a에 존재하는 경우: 해당 요소의 인덱스를 반환 (0부터 시작)
• 요소 key가 배열 a에 존재하지 않는 경우: - (insertion point) - 1을 반환. 이때, insertion point는 key를 삽입해야 할 위치의 인덱스를 나타낸다. (음수 값은 찾지 못한 경우를 나타낸다)

>> 아래와 같은 배열이 있다면 30의 경우 2의 값이 나오고, 25의 경우 -3 - 1 = -4의 값이 나온다.

int[] arr = {10, 20, 30, 40, 50};
Arrays.binarySearch(arr, 30)
Arrays.binarySearch(arr, 25)

 

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