[프로그래머스] '명예의 전당 (1)' - Java

<문제 제시>

<문제설명>
"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 
시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 
매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 
상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 
즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. 
k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 
출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.
이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 
예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 
명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.
명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 
매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

<예시 입출력>

---

<문제 해결 과정>

문제만 보았을땐 단순히 순위를 매기는 경연 프로그램을 만드는 것이라고 생각할 수 있었다.

"어떻게"가 문제였는데, k일까지는 매일 1명의 가수가 노래를 부르므로 k명의 가수가 목록에 담기고,

그 이후로 점수를 정렬하는 문제였다. 가수의 이름이나 가수를 구분하는 내용은 없으므로,

부여된 가수의 점수로 단순히 순위를 매기면 된다고 생각했다.

Try 1) 

for(int j = 0; j < arr.size(); j++) {
    if(score[i] > arr.get(j)) {
        arr.add(j, score[i]);

        // 최하위점수 업데이트
        if(score[i] < min) min = score[i];
        System.out.println(i + "일차 " + "최하위 점수 리셋 = " + min);
        // answer에 더해줌
        answer[i] = min;
        System.out.println(i + "일차 " + "answer 값 = " + Arrays.toString(answer));
    }

    else continue;
}

k일차까지는 초기화 후, k+1일차부터의 로직을 만들어보았다.

min변수로 최하위 값을 업데이트하며 찾아보았지만 오답이었다.

Try 2)

public static int[] solution(int k, int[] score) {
    int[] answer = new int[score.length];

    List<Integer> arr = new ArrayList<>();
    int min = score[0];
    System.out.println(min);

    // k일차까지의 초기값 설정
    for(int i = 0; i < k; i++) {

        arr.add(i, score[i]);
        System.out.println(i + "일차 " + "arr = " + arr);

        // 최하위점수 업데이트
        // - 점수 리스트를 내림차순 정렬
        Collections.sort(arr, Collections.reverseOrder());
        min = arr.get(arr.size()-1);
        if(score[i] < min) min = score[i];
        System.out.println(i + "일차 " + "최하위 점수 리셋 = " + min);

        // answer에 더해줌
        answer[i] = min;
        System.out.println(i + "일차 " + "answer 값 = " + Arrays.toString(answer));

        System.out.println();
    }
    // 여기까지 로직 완료

    System.out.println("기본 2일차까지 완료");

    int j = 0;
    for(int i = k; i < score.length; i++) {


        if(arr.get(j) < score[i]) {

            System.out.println(i + "일차 " + "arr = " + arr);
            j++;

            // 최하위점수 업데이트

            // - 점수 리스트를 내림차순 정렬
            Collections.sort(arr, Collections.reverseOrder());
            min = arr.get(arr.size()-1);
            //if(score[i] < min) min = score[i];
            System.out.println(i + "일차 " + "최하위 점수 리셋 = " + min);

            // answer에 더해줌
            answer[i] = min;
            System.out.println(i + "일차 " + "answer 값 = " + Arrays.toString(answer));

            System.out.println();
            continue;
        }
        answer[i] = min;
        System.out.println(i + "일차 " + "answer 값 = " + Arrays.toString(answer));
        System.out.println();
    }

    // 최하위 점수를 return
    return answer;
}

Collections.sort(arr, Collections.reverseorder())를 통해 점수를 내림차순 정렬하고, 

k+1일차부터의 점수를 계속해서 업데이트해나갔지만 오답이었다.

Solution 1)

먼저 k일차까지 데이터를 단순 추가해주는 부분과

// 인덱스가 k - 1만큼 반복할때는 (k일차까지) - 단순추가
if(i < k - 1) {
    // 단순히 추가하고 내림차순 정렬
    arr.add(score[i]);
    arr.sort(Collections.reverseOrder());

    // answer에는 리스트 끝값 (최하위 점수) 누적
    answer[i] = arr.get(arr.size() - 1);
}

k일차 이상부터는 점수 비교 후 추가하는 부분을 나누어 작성해보았다.

// 인덱스가 k일차 이상부터는 점수 비교 후 넣기
else if(i >= k - 1) {
    arr.add(score[i]);
    arr.sort(Collections.reverseOrder());

    // arr 길이를 k로 고정시킬 필요없이 추가된 값에서 내림차순 정렬 후
    // k-1번째 인덱스가 최하위 값이므로 가져와서 answer에 넣으면 되는 로직
    answer[i] = arr.get(k-1);
}

---

<전체코드>

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class hall_of_fame {

	public static int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        List<Integer> arr = new ArrayList<>();

        // 점수 배열의 길이만큼 반복
        for(int i = 0; i < score.length; i++) {
        	// 인덱스가 k - 1만큼 반복할때는 (k일차까지) - 단순추가
        	if(i < k - 1) {
        		// 단순히 추가하고 내림차순 정렬
        		arr.add(score[i]);
        		arr.sort(Collections.reverseOrder());
        		
        		// answer에는 리스트 끝값 (최하위 점수) 누적
        		answer[i] = arr.get(arr.size() - 1);
        	}
        	
        	// 인덱스가 k일차 이상부터는 점수 비교 후 넣기
        	else if(i >= k - 1) {
        		arr.add(score[i]);
        		arr.sort(Collections.reverseOrder());
        		
        		// arr 길이를 k로 고정시킬 필요없이 추가된 값에서 내림차순 정렬 후
        		// k-1번째 인덱스가 최하위 값이므로 가져와서 answer에 넣으면 되는 로직
        		answer[i] = arr.get(k-1);
        	}
        }
        
        // 각 일차마다의 저장된 최하위 점수를 return
        return answer;
    }

	public static void main(String[] args) {
		// 명예의 전당 목록의 점수 개수
		int k = 3;
		
		// 1일부터 마지막 날까지 출연한 가수들의 점수목록
		int[] score = {10, 100, 20, 150, 1, 100, 200};
		
		System.out.println(Arrays.toString(solution(k, score)));
	}

}

---

answer[i] = arr.get(k-1); 라는 코드를 통해 간단히 코드를 풀어낼 수 있었다.

전체적인 점수를 모두 고려하려고 해서 복잡해진 문제였다. 단순히 가장 최하위 값만 배열에 저장하여 배열을 리턴해주면 되는 문제였다.

 

---

문제링크)
https://school.programmers.co.kr/learn/courses/30/lessons/138477

프로그래머스