๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Programmers

[C++/PGS] Lv.2 : ๋” ๋งต๊ฒŒ (ํž™ Heap)

728x90

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

๋ฌธ์ œ ์„ค๋ช…

๋งค์šด ๊ฒƒ์„ ์ข‹์•„ํ•˜๋Š” Leo๋Š” ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด Leo๋Š” ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋‚ฎ์€ ๋‘ ๊ฐœ์˜ ์Œ์‹์„ ์•„๋ž˜์™€ ๊ฐ™์ด ํŠน๋ณ„ํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ์„ž์–ด ์ƒˆ๋กœ์šด ์Œ์‹์„ ๋งŒ๋“ญ๋‹ˆ๋‹ค.

์„ž์€ ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜ = ๊ฐ€์žฅ ๋งต์ง€ ์•Š์€ ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜ + (๋‘ ๋ฒˆ์งธ๋กœ ๋งต์ง€ ์•Š์€ ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜ * 2)

Leo๋Š” ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๊ฐ€ K ์ด์ƒ์ด ๋  ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜์—ฌ ์„ž์Šต๋‹ˆ๋‹ค.
Leo๊ฐ€ ๊ฐ€์ง„ ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ ๋‹ด์€ ๋ฐฐ์—ด scoville๊ณผ ์›ํ•˜๋Š” ์Šค์ฝ”๋นŒ ์ง€์ˆ˜ K๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด ์„ž์–ด์•ผ ํ•˜๋Š” ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ ์‚ฌํ•ญ
  • scoville์˜ ๊ธธ์ด๋Š” 2 ์ด์ƒ 1,000,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • K๋Š” 0 ์ด์ƒ 1,000,000,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • scoville์˜ ์›์†Œ๋Š” ๊ฐ๊ฐ 0 ์ด์ƒ 1,000,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” -1์„ return ํ•ฉ๋‹ˆ๋‹ค.

 

-1 ์กฐ๊ฑด์„ ์ œ๋Œ€๋กœ ์ฒดํฌํ•˜์ง€ ์•Š์•„์„œ ํ•œ๋ฒˆ ํ‹€๋ ค๋ฒ„๋ ธ๋‹ค

ํ ์•ˆ์— ๋‚จ์€ ์ˆซ์ž๊ฐ€ 2๊ฐœ ๋ฏธ๋งŒ์ผ ๋•Œ, -1์„ ๋ฆฌํ„ดํ•˜๋ฉด ๋œ๋‹ค!

 

 

 

๋‚˜์˜ ํ’€์ด

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int> > pq(scoville.begin(), scoville.end());
    while(1){
        if(pq.top()>=K) break;
        if(pq.size()<2) return -1;
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        int c = a + b*2;
        pq.push(c);
        // cout << c<<"/";
        answer ++;
    }
    
    return answer;
}
728x90