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

gcoco·2023년 5월 10일

안녕하세요! 맛이 아쉬운 점심을 먹어 기분도 아쉬운 GCOCO입니다!

그래서 점심 메뉴는 무엇이었냐.. 바로 제육덮밥 & 냉면이었는데요...
메뉴의 이름 자체는 상당히 괜찮죠? 하지만... 맛이....맛이 아쉬워요!!
간만 되게 짠 제육에 건더기는 양파밖에 없고 팅팅 불은 냉면을 먹으려니 정말 아쉬울 따름이었어요... 뭔가 학식의 맛이 균일하지 않고 스펙트럼이 굉장히 넓은 느낌입니다! 금일의 점심 중에서는 요구르트가 제일 맛있었던것 같네요🥲🥲

본론으로 가보죠!

문제링크:
이 문제는 전에 풀은적이 있는 문제입니다만, 현재 진행하는 과목 중에서 프로그래머스 문제를 다시 풀고있기에 제 옛날 코드와 새로 작성한 코드를 비교하며 발전한 부분이 있는지 확인하며 코드리뷰를 해 보도록 하겠습니다!

우선 구버젼의 코드 입니다.

첫풀이

#include <string>
#include <vector>
#include <queue>
#include <iostream>


using namespace std;

vector<int> solution(int k, vector<int> score) {
    priority_queue<int> pq;
    vector<int> answer;
    int i=0;
    while(i<score.size()){
        if(i<k){
             pq.push(-1*score[i]);
        }
        else{
            if(pq.top()>-1*score[i]){
                pq.pop();
                pq.push(-1*score[i]);
            }
        }
        answer.emplace_back(-1*pq.top());
        i++;
    }
    return answer;
}

이럴수가 이렇게 어렵게 풀었다고?
무려 priority_queue를 사용하여 풀었습니다!
코드의 흐름은 다음과 같습니다.

pq를 이용할 것이다. i는 pq의 size()를 확인하기 위한 용도
score를 순회하며 -1을 곱하여 값을 넣어준다 :
이유는 priority_queue는 내부에서 자동정렬이 되는데 우선순위가 높은 기준입니다! 그렇기에 넣는값에 -1을 곱해주면, 절대값이 작은 값이 우선순위가 가장 높은 pq.top()에 위치하게 되는것이지요.
만약 pq가 다 차면 새로 들어온 값이 top의 값보다 작은지(절대값) 확인하고 pq의 top을 제거하고 넣는다.
answer의 pq의 top(가장 낮은 점수) *(-1) 해주어 answer에 넣는다.
i의 인덱스를 증가시킨다.

확실히 실력이 부족할 때 풀었던 풀이라서 그런지 다시 푼 풀이보다 훨씬 불편하게 풀었다고 생각합니다. 괜히 어렵게 풀었다라는 말이 잘 어울립니다. 개선점을 보면 다음과 같습니다.

pq를 오름차순 형태로 구현한다 , pq.size()를 이용해 사이즈를 측정한다.
pq를 안쓴다!

새로운 풀이, 같이 한번 보시죠!

새로운 풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    vector<int> honor;
    for(auto i:score){
        honor.emplace_back(i);
        sort(honor.rbegin(),honor.rend());
        if(honor.size()>k)
            honor.pop_back();
        answer.emplace_back(honor.back());
    }
    
    return answer;
}