[프로그래머스] 코딩테스트 연습 - 명예의 전당(1) (Java, C)

-링크

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

프로그래머스

 

 

-문제 설명

"명예의 전당"이라는 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 함수를 완성해주세요.

 

 

-제한 사항

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

 

 

-입출력 예

3	[10, 100, 20, 150, 1, 100, 200]	[10, 10, 10, 20, 20, 100, 100]
4	[0, 300, 40, 300, 20, 70, 150, 50, 500, 1000]	[0, 0, 0, 0, 20, 40, 70, 70, 150, 300]

 

 

-Java 해설

이 문제를 풀면서 Array를 쓸까 ArrayList를 사용할까 고민하고 적용 해 보느라 시간이 좀 소요가 됐었다.

우선 return될 Array의 원소 개수는 들어 온 Array의 원소 개수와 같다.

매 점수가 집계 될 때 마다, 탑 K의 가장 낮은 점수를 구해야 하기 때문에 같은 것이다. 

정리를 해 보았을 때, topK를 담을 ArrayList를 준비하고 들어온 점수 순서대로 K번째 까지는 list에 그대로 담으면서 내림차순으로 정렬 해 준다. 

ArrayList가 아닌 Array를 사용했을 땐 미리 Array 배열의 개수를 K개로 할당 해 놔서 그런지 원소가 들어올 때 마다 내림차순으로 정렬을 해야 하는데 그 때 outofindex에러가 계속 발생해서 ArrayList로 대체하였다. 

내림차순으로 정렬을 원소가 들어올 때 마다 정렬을 해 놓았기 때문에 맨 마지막 인덱스가 topK의 가장 작은 수 인 것을 알 수 있다.

그러므로, topK의 마지막 원소(제일 작은 점수)는 answer 배열에 항상 담도록 하고, Score의 K번째 원소 부터는 topK의 마지막 원소(제일 작은 점수)보다 클 경우에만 topK의 원소로 집어넣도록 하였다.

최대한 객체지향을 활용 해 보고자, topK에 넣는 함수와 값을 정렬하여 최소 값을 얻는 함수로 구성하여 문제를 풀어내었다.

여기에서 항상 마지막 원소를 구할 때 원소의 번호를 topK.length-1로 준 이유는 리스트의 번호는 0부터 시작되기 때문에 리스트의 마지막 원소는 10개의 원소가 들어있을 경우 10개 -1인 9번 이기 때문이다.

문제 풀이 후 다른 사람의 풀이에서 PriorityQueue를 이용해서 문제를 푼 것을 보았다. 다음에 이런 문제를 맞닥드렸을 땐 이 것을 이용해서 풀어내면 간단하게 풀어낼 수 있을 것 같다. 

 

 

 

-풀이(Java)

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    ArrayList<Integer> topK = new ArrayList<>(); 
    int cnt;
    int topCnt;
    
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        int min = 0;    
        topCnt = k;
        
        for(int i = 0; i < score.length; i++){ 
            putTopK(score[i]);
            answer[i] = calcMin();
        }
        
        return answer;
    }
    
    public void putTopK(int score){  
        if(topK.size() < topCnt){
            topK.add(score);
        }else{
            if(topK.get(topK.size()-1) < score){
                topK.remove(topK.size() - 1);
                topK.add(score); 
            }
        }    
    }
    
    public int calcMin(){
        Collections.sort(topK, Collections.reverseOrder());  
        return topK.get(topK.size() -1);
    }
}

 

 

-C 해설

answer 배열의 개수는 매 점수 집계 마다 topk의 최소 점수를 넣어야 하므로, score의 개수와 동일하다.

answer의 메모리 할당을 score의 개수와 동일하게 해 주고, topK를 집계 할 배열을 k만큼 할당 해 준다.

k가 topK의 마지막 원소 번호이므로 score로 for문을 돌릴 때 k보다 작을 땐 topK의 i번째 위치에 원소를 넣어주고, k보다 i가 커졌을 땐 

원소를 넣을 때 마다 내림차순으로 정렬을 하여 마지막 원소(제일 작은 원소)보다 클 경우 마지막 원소와 바꿔준다.

정렬의 경우 qsort를 사용 해 주었는데, qsort에는 배열과 배열 원소의 개수를 또는 정렬할 위치의 원소를 넣어주어야 하기 때문에 k를 넘겨 정렬한다(아직 채워지지 않은 원소의 경우 처음 메모리 할당을 할 때 0으로 초기화 되므로 제약사항에 score은 음수가 나오는 경우가 없으니 채워지지 않은 점수는 0이므로 자연스레 맨 마지막 원소로 위치하게 됨).

 

 

-풀이(C)

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int static topK_ASC (const void* a, const void* b)
{
    if (*(int*)a < *(int*)b)
        return 1;
    else if (*(int*)a > *(int*)b)
        return -1;
    else
        return 0;
}
// score_len은 배열 score의 길이입니다.
int* solution(int k, int score[], size_t score_len) {
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    int* answer = NULL;
    int* topK = NULL;
    int i = 0;
    
    answer = (int*)malloc(sizeof(int)*score_len);
    memset(answer, 0, sizeof(int)*score_len);
    topK = (int*)malloc(sizeof(int)*k);
    memset(topK, 0, sizeof(int)*k);
    
    for(i = 0; i < score_len; i++){
        if(i < k){
            topK[i] = score[i];
            qsort(topK, k, sizeof(int), topK_ASC);
            answer[i] = topK[i];
        }else{
            if(topK[k-1] < score[i])
                topK[k-1] = score[i];
            qsort(topK, k, sizeof(int), topK_ASC);
            answer[i] = topK[k-1];
        }        
    }

    return answer;
}