Lv1_[명예의 전당(1), C++] 풀이 및 알고리즘 정리 - 프로그래머스

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

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

※ 동료와 코드 리뷰 후 우선순위 큐를 활용해보라는 의견을 듣고 내용 추가

 

두 가지의 풀이 방식

1. 정렬 함수 (sort)
2. 우선순위 큐 (Priority Queue)

 

1. 처음 풀었던 sort를 이용한 풀이 방식

  1) score 점수 비교
    1-1) 최하위 저장된 점수 개수가 k개를 넘지 않을때 → 2-1)으로 이동
    1-2) k를 넘거나 같을 때 → 2-2)으로 이동

  2) score 저장 후 값 추출
    2-1) score를 임시저장소(tmp)에 넣고 내림차순 정렬 후 맨끝에 값을 추출

          ※ (score > min_value)리면 정렬은 하지 않아도됨

    2-2) (score > min_value)라면 최하위 점수가 바뀌게 됨
            tmp에 score를 넣고 내림차순 정렬 후 k번째 값을 추출

  3) score가 없을 때까지 1)부터 반복 실행

 

- sort 함수 활용 풀기

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    vector<int> tmp;
    int min_value;
 
    tmp.push_back(score[0]);
    min_value = score[0];
    answer.push_back(min_value);
 
    for(int i = 1; i < score.size(); i++) {
        if(i < k) {
            tmp.push_back(score[i]);
            if(score[i] > min_value) {
                sort(tmp.begin(), tmp.end(), greater<int>());
            }
            min_value = tmp.back();
        } else {
            if(score[i] > min_value) {
                tmp.push_back(score[i]);
                sort(tmp.begin(), tmp.end(), greater<int>());
            }
            min_value = tmp[k-1];
        }
        answer.push_back(min_value);
    }
 
    return answer;
}

 

2. 우선순위 큐를 이용한 풀이 방법 (greater<int>로 Min Heap으로 구성)

  1) score 점수 비교
    1-1) 최하위 저장된 점수 개수가 k개를 넘지 않을때 → 2-1)으로 이동
    1-2) k를 넘거나 같을 때 → 2-2)으로 이동

  2) score 저장 후 값 추출
    2-1) score를 우선순의큐(pq)에 넣고 맨끝에 값을 추출( pq.top() )

    2-2) (score > min_value)라면 최하위 점수가 바뀌게 됨
            pq에 score를 넣고 pq.pop으로 가장 낮음 점수를 삭제 후 맨끝에 값을 추출( pq.top() )

  3) score가 없을 때까지 1)부터 반복 실행

 

- 우선순위 큐로 풀기

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    priority_queue<int, vector<int>, greater<int>> pq;
    int min_value;
 
    for(unsigned int i = 0; i < score.size(); i++) {
        if(i < k) {
            pq.push(score[i]);
            min_value = pq.top();
        } else {
            if(score[i] > min_value) {
                pq.push(score[i]);
                pq.pop();
            }
            min_value = pq.top();
        }
        answer.push_back(min_value);
    }
    
    return answer;
}
 

 

sort함수 보다 우선순위 큐가 효율이 더 좋음

 

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓