[힙] 더 맵게

yerin6860·2020년 8월 7일
0

프로그래머스

목록 보기
7/30
post-thumbnail

|| 문제설명 ||

  1. 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶어한다.

  2. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다.

    섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

  3. Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

  4. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성하라.

  • scoville : Leo가 가진 음식의 스코빌 지수를 담은 배열
  • K : 원하는 스코빌 지수

    _ scoville의 길이 : 2 이상 1,000,000 이하
    _ K : 0 이상 1,000,000,000 이하
    _ scoville의 원소: 0 이상 1,000,000 이하
    _ 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1을 return


|| 문제해결방법 ||

- 우선순위큐 <int> 형의 변수를 선언하여 scoville의 모든 원소 push
- 정렬된 상태의 원소들을 앞에서부터 차례로 만들기
- 새롭게 만든 스코빌 지수는 변수에 추가해 주고 계속 반복해 나감
- 섞을 때마다 answer을 증가시켜줌

|| 코드 ||

[2020.08.08] 실패
#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(auto i = scoville.begin(); i != scoville.end(); i++) {
        pq.push(*i);
    }
    for(int i=0; i<pq.size()+answer; i++) {
        if(pq.top() < K) {
            int tmp = pq.top();
            pq.pop();
            pq.push(tmp + pq.top() * 2);
            pq.pop();
            answer++;
        }
    }
    return answer;
}

  • 문제 이해부족 : "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다."의 조건 누락
[2020.08.08] 성공
- 스코빌 지수를 만족하지 못하는 원소가 하나만 남았을 때 return -1;
#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(auto i = scoville.begin(); i != scoville.end(); i++) {
        pq.push(*i);
    }
    for(int i=0; i<pq.size()+answer; i++) {
        if(pq.top() < K) {
            if(i == pq.size()+answer - 1) {
                return -1;
            }
            int tmp = pq.top();
            pq.pop();
            pq.push(tmp + pq.top() * 2);
            pq.pop();
            answer++;
        }
    }
    return answer;
}

0개의 댓글