Table of Contents
문제
원문 보기 : [LeetCode] 1962. Remove Stones to Minimize the Total
0부터 인덱스가 시작하는 배열 piles와 k가 주어진다. piles[i]는 i번째 돌무더기의 돌 개수를 의미한다. 이제 다음 연산을 정확히 k번 수행해야 한다.
- 어떤 돌무더기
piles[i]를 골라floor(piles[i] / 2)만큼 돌을 뺀다.
같은 돌무더기에 대해 여러 번 연산을 수행할 수 있다.
k번의 연산 후 남은 돌무더기의 합이 최소가 되게 만들면 된다.
floor(x)는 x보다 작거나 같은 것 중 가장 큰 정수를 의미한다.(내림 연산과 같음)
조건(Constraints):
1
2
3
1 <= piles.length <= 105
1 <= piles[i] <= 104
1 <= k <= 105
예제
Example 1
Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [5,4,5].
- Apply the operation on pile 0. The resulting piles are [3,4,5].
The total number of stones in [3,4,5] is 12.
Example 2
Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [4,3,3,7].
- Apply the operation on pile 3. The resulting piles are [4,3,3,4].
- Apply the operation on pile 0. The resulting piles are [2,3,3,4].
The total number of stones in [2,3,3,4] is 12.
계획
- 내가 이해한 것
매 반복마다 배열에서 가장 큰 수를 찾아서 반토막내면 된다. 고로 매번 가장 큰 수를 찾아내면 된다. - 약간의 사고가 있었음
블로그에 올릴 글을 쓰면서 문제를 풀려고 태그를 봤다가 힙을 쓰면 된다는 것을 스포일러당했다. 최댓값을 일일이 찾을 생각만 했지 힙을 쓸 생각은 전혀 못하고 있었다. - 타협
내가 스포일러를 당했든 그렇지 않았든, 처음에는 분명 배열에서 일일이 최댓값을 찾는 방법을 시도했을테니 먼저 한번 틀려보고 힙을 사용하자. 직접 만든 힙 말고 STL 우선순위 큐 쓸 생각이다. - 계획
(1) : 배열을 이용해 매번 최댓값을 찾아 연산한다.
(2) : 우선순위 큐를 이용해 최대힙을 만들고 지정된 횟수만큼 pop한다.
풀이
1. 배열과 최댓값
결과 : 시간초과
풀이 방식 : 매 연산마다 최댓값을 직접 찾는다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int minStoneSum(vector<int>& piles, int k) {
int total = 0; // 총합
for (int i = 0; i < k; i++) { // 돌무더기 덜어내기 연산
int max_idx = max_index(piles);
piles[max_idx] -= piles[max_idx] / 2;
}
for (int& n : piles) // 총합 구하기
total += n;
return total;
}
int max_index(vector<int>& piles) { // 배열 내에서 최댓값 찾기
int idx = 0;
for (int i = 1; i < piles.size(); i++) {
if (piles[i] > piles[idx])
idx = i;
}
return idx;
}
};
2. 우선순위 큐
Runtime : 755 ms
Memory : 98.7 MB
리뷰
- 자료구조 이론만 배웠지 써먹을 줄은 하나도 모르고 있다(제일 중요함). 매번 최댓값이 필요한데 정렬은 아냐? 그럼 당연히 적어도 최댓값만은 보장되는 자료구조를 생각해 봐야지 매번 최댓값 찾기가 뭡니까 학생. 그나마 그 방법이 당연히 시간초과로 틀릴 거라는 예상은 할 줄 아니 됐습니다.
greater<int>는 오름차순 정렬에 쓴다.priority_queue기본값은 내림차순. 이걸 헷갈려서 한 번 틀렸다(예제 틀려서 기록은 안 남음). 벡터로 큐 초기화하는 방법은 덤이다.- 처음 주어진 배열의 순서를 그대로 유지하지 않아도 풀이가 가능했다. 배열을 큐에 모두 넣고 이후로 큐에 있는 값만 사용하면서 배열의 원형이 완전히 사라지는데, 해답의 조건이 총합이기 때문에 배열을 유지하지 않아도 무방하다. 이런 풀이를 처음 해봐서 신기하다고 쓰는 거다.
원래는 배열을 유지해가면서 답을 구할 생각으로 배열과 인덱스를pair로 만들어서 큐에 넣고 계산은 배열에 직접 할 생각이었는데, 그렇게 하면 우선순위 큐를 처음 만들 때 배열의 크기만큼 반복문을 돌아야 한다. 배열을 그대로 넣으면 내부적으로는 당연히 heapify 연산을 하겠지만 적어도 내가 쓰는 코드는 한 줄, 한 번의 실행으로 끝나는데 pair를 만들어서 넣으면 배열 원소 개수만큼 힙 삽입 연산을 해야 하니까 당연히 손해다. 그래서 왠지 될 것 같아서 우선순위 큐 초기화하는 방법을 찾아봤었다.
우선순위 큐 초기화 참고 : std::priority_queue::priority_queue - 처음에 문제를 약간 잘못 이해한 부분이 있었다. 돌무더기를 덜어내는 연산을 할 때, C++ 기준으로 정수를 그냥 2로 나누기만 하면 숫자가 홀수일 때 답이 틀리게 된다. 문제에서 요구한 것은 해당 수를 2로 나누고 내림한 값을 원래 수에서 빼라는 것이었고, 나는 빼야 할 수가 답이라고 잘못 이해했었다. 이것도 예제에서 틀린 거라 기록은 남지 않았다.
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
// #include <iostream>
// #include <queue>
// #include <vector>
// using namespace std;
class Solution {
public:
int minStoneSum(vector<int>& piles, int k) {
priority_queue<int> que(piles.begin(), piles.end()); // 주어진 배열의 값들로 이루어진 우선순위 큐(내림차순) 생성
int total = 0; // 총합
for (int i = 0; i < k; i++) { // 돌무더기 덜어내기 연산
int num = que.top(); // top은 항상 최댓값이다
que.pop(); // top이 자동으로 pop을 수행하지 않기 때문에 따로 해줘야 함.
que.push(num - num / 2); // 아까 그 top에 돌무더기 덜어내기 연산을 수행한 후 다시 큐에 넣는다
}
while(!que.empty()) { // 총합 구하기 : 모든 연산을 큐에 있는 값으로 했기 때문에 더할 때도 큐에 있는 값을 써야 한다
total += que.top();
que.pop();
}
return total;
}
};
참고 자료
[1] std::priority_queue::priority_queue, https://cplusplus.com/reference/queue/priority_queue/priority_queue/