더 맵게 - 프로그래머스, c++

 

 

- 문제 풀이

"힙(Heap)"을 사용하는 문제였다.

문제를 풀기 전 힙의 개념에 대해 알아보았다.

https://doorrock.tistory.com/13

https://yabmoons.tistory.com/374

힙은 완전 이진 트리 자료구조로 왼쪽에서부터 아래로 빈 곳없이 값이 저장된다.

Minheap은 부모 노드의 값은 자식 노드의 값보다 항상 작다.

Maxheap은 부모 노드의 값은 자식 노드의 값보다 항상 크다.

따라서 숫자가 정렬되는 효과가 있다. (하지만 힙은 형제노드끼리는 값 비교 안 함, 오로지 부모-자식만)

Minheap의 루트노드에는 최솟값이, Maxheap의 루트노드에는 최댓값이 있게 된다.

맨 끝에 값을 insert한 후 순서에 맞게 정렬한다. (말단부터 값을 비교해 나감)

pop을 하면 트리의 제일 위에 루트노드 값이 나가게 된다. (최상단부터 값을 비교하며 트리 모양을 다시 잡음)

 

힙은 주로 우선순위 큐를 구현하기 위해 사용된다.

(큐는 push, pop, size, front를 우선순위 큐는  push, pop, size, top을 씀)

#include <queue>로 간단하게 구현 가능하다.

우선순위 큐 내림차순으로 선언.

priority_queue<int> p_qu_l;

우선순위 큐 오름차순으로 선언.

priority_queue<int, vector<int>, greater<int>> p_qu_g;

우선순위 큐에 pair 만들어 활용하기 (첫번째 int값 크기 순대로 내림차순으로 정렬됨)

	priority_queue<pair<int,int>> temp;
	temp.push(make_pair(3,100));

cout << temp.top().first << ',' << temp.top().second << '\n';

 

 

- 코드

제출한 코드는 다음과 같다.

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

int solution(vector<int> scoville, int K) {
    //반환 값 선언, 음식 섞은 횟수
    int answer = 1;
    
    //힙 생성
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=0; i<scoville.size(); i++) {
        pq.push(scoville[i]);
    }
    
        //값들이 K를 넘지 않는지 넘는지 확인
        bool makeK = true;
        for(int i=0; i<pq.size(); i++) {
            if(K > pq[i]) {
                makeK = false;
                break;
            }
        } 
        if(makeK) {
            answer = 0;
            return answer;
        }
    
    //반복문 실행하며 음식 섞기
    while(answer<=scoville.size()-1) {     
        //음식 섞기
        int n1 = pq.top();
        pq.pop();
        int n2 = pq.top();
        pq.pop();
        pq.push(n1+(n2*2));
        
        //값들이 K를 넘지 않는지 넘는지 확인
        bool makeK = true;
        for(int i=0; i<pq.size(); i++) {
            if(K > pq[i]) {
                makeK = false;
                break;
            }
        }
        
        //K를 넘지 않는 수가 있다면 반복문 다시 실행
        if(!makeK) {
            answer++;
        }
        else
            break;
        
        if(answer>=scoville.size())
            return -1;
    }
    
    return answer;
}

 

 

하지만 #include <queue>의 큐에서는 탐색기능을 사용할 수 없어 pq[i]부분에서 오류가 났다.

이를 해결하기 위해서는 deque, list, vector 등을 사용해야 했다.

그래서 우선순위 큐(힙)을 사용할 수 있는 방법이 있다.

<수정 사항>

1. for문을 통해 pq[i] 형식으로 우선순위 큐에 접근하는 방법보다, miniheap의 성질을 활용하여 pq.top()에 있는 수만 K이상인지를 확인하는 방식으로 대체할 수 있다.

2. while 반복문의 조건을 수정하였다.

음식섞기를 수행할 때 마다 pop이 되어 큐 안에 들어있는 수가 줄어들는데 이를 이용해 pq.size()>1이라는 조건으로 대체했다.

(위에 처럼 answer가 원하는 값을 가질 때까지 while반복문을 돌리고 만족되면 break하는 식의 방법은 좋지 않은 방법이다.)

수정후 제출한 코드는 다음과 같다.

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

int solution(vector<int> scoville, int K) {
    //반환 값 선언, 음식 섞은 횟수
    int answer = 0;
    
    //힙 생성
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=0; i<scoville.size(); i++) {
        pq.push(scoville[i]);
    }
    
    //반복문 실행하며 음식 섞기
    while(pq.size()>1 && pq.top()<K) {     
        //음식 섞기
        int n1 = pq.top();
        pq.pop();
        int n2 = pq.top();
        pq.pop();
        pq.push(n1+(n2*2));
        answer++;
    }
    
    //계산 값 반환하기
    if(pq.top()<K) 
        return -1;
    else 
        return answer;
}