본 문제는 level2인 것 치고는 쉬운 편이었지만 문제를 꼼꼼히 읽어야했던 문제였다. 나는 함께 문제를 푸는 언니가 문제를 자세히 봐야한다고 말해주었기 때문에 금방 찾을 수 있었지만, 만약 몰랐다면 문제를 제대로 안읽고 왜 안되냐며 헛수고를 하고 있었을거라는 생각이 들었다. 그리고 이번 문제에서는 ‘힙’ 이라는 새로운 자료구조(?)를 배웠는데 처음이라서 쓰는 방법에 대해 조금 헤맸던 것 같다.
1. 문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.
모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
1
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
제한조건
- scoville의 길이는 1 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
2. 알고리즘! 생각해보자
scoville를min-heap으로 만든다.- 가장 작은 스코빌 지수가 K 이하, 음식을 섞어 스코빌 지수를 높이기 때문에 벡터 크기가 2 이상인 동안 다음을 반복한다.
- 가장 작은 스코빌 지수
smallest1과 그 다음으로 작은 스코빌 지수smallest2를 pop한다. - 섞은 음식의 스코빌 지수를 다시
heap에 넣고answer는 증가시킨다. - 반복문이 끝나고, 가장 작은 스코빌 지수가 K보다 작은 경우에 -1을 반환한다.
(이 경우는 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우이다) - 그렇지 않으면 음식을 섞어 K이상의 스코빌 지수를 만들었기 때문에 섞은 횟수
answer를 반환한다.
3. 해결코드
[C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <algorithm>
#include <vector>
using namespace std;
int solution(vector<int> scoville, int K) {
int answer = 0;
make_heap(scoville.begin(),scoville.end(), greater<int>());
while(scoville.front() < K && scoville.size() >= 2) {
pop_heap(scoville.begin(),scoville.end(), greater<int>());
int smallest1 = scoville.back();
scoville.pop_back();
pop_heap(scoville.begin(),scoville.end(), greater<int>());
int smallest2 = scoville.back();
scoville.pop_back();
scoville.push_back(smallest1 + smallest2 * 2);
push_heap(scoville.begin(),scoville.end(), greater<int>());
answer ++;
}
if (scoville.back() < K) return -1;
return answer;
}
4. 해결능력UP, 깊이 생각해보기
heap자료구조를 쓰기위해서 어떻게 해야하나?- default는 max-heap, min-heap을 만드려면?
heap자료 구조를 어떻게 사용하는지!- 다른 사람이 푼 코드를 보니
make_heap()외에 아예priority_queue의 자료구조를 사용!
5. 참고해서 문제해결 ٩( ᐛ )و
- [C++ 공식 문서] std:make_heap http://www.cplusplus.com/reference/algorithm/make_heap/
make_heap(),pop_heap()등의 관련 함수들을 사용하기 위해서는#include <algorithm>
- STL) Heap 과 관련된 연산들 https://openmynotepad.tistory.com/35
make_heap()함수는 임의 반복 접근자가 있는 모든 컨테이너를 heap으로 변환
- [StackOverFlow] Comparator for min-heap in C++
https://stackoverflow.com/questions/14016921/ comparator-for-min-heap-in-cmake_heap()함수는 기본적으로 max-heap을 생성, min-heap을 생성하기 위해서는 세 번째 인자로 비교 함수greater<int>()할당
1
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges