[프로그래머스][java] lv 0 진료순서 정하기

1. 문제 설명

2. 나의 풀이

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int[] solution(int[] emergency) {
        int size = emergency.length; 

        Integer[] sorted = new Integer[size]; //크기대로 정렬된 emergency 배열

        int[] answer = new int[size];//인덱스가 들어갈 답 배열

        for(int i = 0; i < size; i++)
        {
            sorted[i] = emergency[i];
        }

        Arrays.sort(sorted, Collections.reverseOrder());//emergency 배열 정렬

        for(int i = 0; i < size; i++)
        {
            for(int j = 0; j < size; j++)
            {
                if(sorted[i] == emergency[j])
                {
                    answer[j] = i+1;
                }
            }
        }

        return answer;
    }    
}

 

1. emergency 배열 원소를 크기대로 내림차순 정렬

2. 정렬된 배열과 원래 배열원소를 비교 

3. 정답배열의 원래 배열원소가 있던 위치(j번지)에 i(정렬된 배열원소 위치, 즉 크기 순서)+1(0부터 시작했으므로) 대입

 

arrays.sort 를 거꾸로(내림차순) 정렬하려면 Arrays.sort(sorted, Collections.reverseOrder());

를 사용하면 되는데, 여기서 sorted는 객체타입이어야함

즉 int [] sorted는 저기 들어갈 수 없다. int는 원시타입!

Integer로 바꿔주면 됨.

3. 다른 사람의 풀이

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

        for(int i = 0; i < answer.length; i++){
            if(answer[i] != 0){
                continue;
            }
            int idx = 1;
            for(int j = 0; j < answer.length; j++){
                if(emergency[i] < emergency[j]){
                    idx++;
                }
            }
            answer[i] = idx;
        }
        return answer;
    }
}

순위의 기본값은 1이고

emergency[i] < emergency[j] 를 비교하여 자기보다 큰 숫자가 있는지 서치함

자기보다 큰 숫자를 만나면 idx를 증가시킴(하나씩 밀림).

정렬된 배열이 필요하지 않고 순위를 바로바로 답 배열에 저장할 수 있는 깔끔한 코드다.

  if(answer[i] != 0){
                continue;
            }

다만 이 부분은 왜 있는지 모르겠어서 빼 봤는데 딱히 아무 차이 없는듯..

 

3-1. 다른사람의 코드 2

import java.util.*;
class Solution {
    public int[] solution(int[] emergency) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] emergencySort = Arrays.copyOfRange(emergency, 0, emergency.length);
        Arrays.sort(emergencySort);
        int size = emergency.length;
        for(int i = 0; i<emergencySort.length; i++){
            int e = emergencySort[i];
            map.put(e, size-i);
        }
        for(int i = 0; i<emergency.length; i++){
            emergency[i] = map.get(emergency[i]);
        }
        return emergency;
    }
}

배열 크기가 커질 수록 이중 포문보다 해시맵이 효율적.

위 쪽 이중포문 코드

- 시간 복잡도: O(n^2)
(두 개의 반복문이 중첩되어 n개의 요소에 대해 모든 요소를 비교함)

아래 쪽 해시맵 코드

 

• 정렬: Arrays.sort()를 사용하여 O(n log n)의 시간 복잡도.
• HashMap 삽입 및 조회:
  • HashMap의 삽입과 조회는 평균적으로 O(1)이므로, 두 번의 단일 루프에서 각기 O(n)
• 총 시간 복잡도: O(n log ⁡n)+O(n)+O(n) = O(n log n).

예시로 비교

개선 코드는 HashMap 과 정렬을 사용하여 효율적인 시간 복잡도를 가지며, 대규모 데이터 처리에 적합.