[프로그래머스] 명예의 전당 (1) 자바, 최소값, 정렬

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

프로그래머스

문제

일자별 점수 모음 score, 명예의 전당에 등재되는 갯수 k가 있다.

하루에 점수 하나씩 명예의 전당에 등록하며, k가 가득찬 경우, 최하점을 제거하고 새로운 점수를 내림차순으로 등록한다.

일자별 최하점을 기록하여 int[]로 반환할 것.

제한사항

3 ≤ k ≤ 100
7 ≤ score의 길이 ≤ 1,000
0 ≤ score[i] ≤ 2,000

접근

score을 순회하며 i < k 까지는 우선 점수를 명예의 전당에 등록시키고 

그 이후 내림차순 정렬한 배열의 마지막 값과 새로운 점수를 비교하여 마지막 값이 작으면

for문으로 새 점수가 기존 명예전당 값보다 클 때, 기존 명예의 전당값을 하나씩 뒤로 밀고, 명예전당 맨 앞에 새로운 값을 넣는다.

 

명예의 전당 정리가 끝났다면 Integer.MAX_VALUE와 명예의전당값 중 최소값을 찾아 answer에 넣도록 처리하였다.

 

코드

public static int[] solution(int k, int[] score) {
        Integer[] fames = new Integer[k];
        int[] answer = new int[score.length]; // 결과 배열은 입력 score 길이만큼
        int min = 0;

        for (int i = 0; i < score.length; i++) {
            // 명예의 전신 업데이트
            if (i < k) {
                // 초기 k일 동안은 무조건 추가
                fames[i] = score[i];
            } else {
                Arrays.sort(fames, Collections.reverseOrder());
                // 새로운 점수가 현재 최소값보다 큰 경우만 처리
                if (score[i] > fames[k-1]) {
                    int idx = 0;
                    // 기존 값들을 한 칸씩 뒤로 이동
                    for (int j = k-1; j > 0; j--) {
                        fames[j] = fames[j-1];
                    }
                    fames[idx] = score[i]; // 새로운 최고점을 맨 앞에 삽입
                }
            }

            // 현재 명예의 전신에서 최소값 찾기
            min = Integer.MAX_VALUE;
            for (int j = 0; j < Math.min(i+1, k); j++) {
                min = Math.min(min, fames[j]);
            }
            answer[i] = min;
        }

        return answer;
    }

 

발견된 문제

문제의 요구사항은 해결할 수 있었으나, 로직이 문제의 흐름과 완전히 동일하지 않음
-> score[i]가 최대값보다 작지만 최소값 보다 클 경우의 처리과정이 예상과 다름

 

이 문제를 해결하기 위해, 문제에서 별도로 명예의 전당의 정렬까지 요구하진 않았으므로 정렬구문과 한 칸씩 뒤로 밀어내는 구문을 제거하였다.

대신 명예의전당 값을 바꾸기 전에 최소값과 최소값의 위치를 찾아두고 그 위치에 새로운 값을 넣도록 변경했다.

만약 정렬을 요구한다면 Arrays.sort 나 Arrays.sort(배열, Collections.reverseOrder()); 을 추가하여 처리하면 될 것 같다.

 

수정한 코드

public static int[] solution(int k, int[] score) {
        Integer[] fames = new Integer[k];
        int[] answer = new int[score.length]; // 결과 배열은 입력 score 길이만큼
        int min = 0;

        for (int i = 0; i < score.length; i++) {
            // 명예의 전신 업데이트
            if (i < k) {
                // 초기 k일 동안은 무조건 추가
                fames[i] = score[i];
            } else {
                // 1. 현재 명예의 전신에서 최소값 찾기 (정렬 없이)
                int currentMin = Integer.MAX_VALUE;
                int minIndex = 0;
                for (int j = 0; j < k; j++) {
                    if (fames[j] < currentMin) {
                        currentMin = fames[j];
                        minIndex = j;
                    }
                }

                // 2. 새로운 점수가 최소값보다 큰 경우만 처리
                if (score[i] > currentMin) {
                    fames[minIndex] = score[i]; // 최소값을 새 점수로 교체
                }
            }
//            else {
//                Arrays.sort(fames, Collections.reverseOrder());
//                // 새로운 점수가 현재 최소값보다 큰 경우만 처리
//                if (score[i] > fames[k-1]) {
//                    // 기존 값들을 한 칸씩 뒤로 이동
//                    for (int j = k-1; j > 0; j--) {
//                        fames[j] = fames[j-1];
//                    }
//                    fames[0] = score[i]; // 새로운 최고점을 맨 앞에 삽입
//                }
//            }

            // 현재 명예의 전신에서 최소값 찾기
            min = Integer.MAX_VALUE;
            for (int j = 0; j < Math.min(i+1, k); j++) {
                min = Math.min(min, fames[j]);
            }
            answer[i] = min;
        }

        return answer;
    }

 

알게 된 점

최소값과 최소값의 위치 구하기 : 
    최소값 = Integer.MAX_VALUE와 위치변수 = 0을 선언한 후 반복문으로 순회해 배열값 < 최소값인 경우
    최소값을 갱신하고 해당 위치를 위치변수에 저장한다.

배열의 정렬 (Integer)
    오름차순 : Arrays.sort(배열)
    내림차순 : Arrays.sort(배열, Collections.reverseOrder());