카드 정렬하기
메모
정렬된 배열 2개, 각 수는 a, b
둘을 합쳐서 정렬하려면 a+b만큼의 비교가 필요(=브루트포스)
결국 이거도 각 수가 들어있는 배열을 정렬시키고 앞에서부터 더해나가는거아님?
내가 놓친거
- 나는 단순하게 입력 배열 정렬시켜놓고
- 앞에서부터 더해나가면 된다고 생각
- 예를들면
4
30
40
50
100
일 경우, =30+40 + 70+50 + 120+100
답: 410 - 하지만 아래 테케의 경우 이렇게 풀면답이 아님
4
30
40
50
60
일 경우, 내가 푼 답 = 30+40 + 70+50 + 120+60 = 370
하지만 정답: 360- 해당 테케보며 찾은 문제점
- 더해서 나온 새로운 값을 기존에 저장된 값과 함께 min값 2개를 더해줘야함
- 새롭게 더해나가기만 하면 안됨
- 뭔소리냐면
[30, 40, 70]에서 [30, 40, 70, 50, 120]하고
[30, 40, 70, 50, 120] -> [30, 40, 70, 50, 120, 60]넘어갈 때
50이랑 60이 더 가까워서 50+60=110 을 먼저 계산하고, 110을 더해주는게 이득인데
내가 한 방식은 70+50=120 계산해서 더 큰 120을 더해주게되버림
해답 : 자료형을 바꿔줘야할듯? 그래서 다들 heapq 썼구나...!
set은 중복제거돼서 안됨!
히든 테케 - 없으면 못품;;
4
30
40
50
100
답: 410
4
30
40
50
60
답: 360
8
30
40
50
20
10
100
60
120
답: 1160
8
30
40
50
20
10
100
60
10
답: 860
4
120
40
100
20
답: 500힙 사용법
- 파이썬
-
기본적으로 min-heap
- max-heap으로 만들고 싶다면
import heapq arr = [] heapq.heappush(arr, -num) # 음수로 넣고 num = -heapq.heappop(arr) # 밖에다 음수로 빼야함
-
- C++
-
기본적으로 max-heap
- min-heap으로 만들고 싶다면
priority_queue <int> arr; arr.push(-num); // 음수로 넣고 a = -arr.top(); // 밖에다 음수로 빼야함 arr.pop(); // c++의 pop()은 리턴값이 없음!!
-
솔루션 코드 - 내가 다시 푼
import heapq
import sys
input = sys.stdin.readline
n = int(input())
arr = [int(input()) for _ in range(n)]
heapq.heapify(arr) # 리스트릴 힙으로 변환(-> pop 시 min값 출력)
ans = 0
# 힙에 데이터 2개 이상 있어야 돌릴 수 있다.
while len(arr)-1 != 0:
a = heapq.heappop(arr) # min값 두 개를 추출
b = heapq.heappop(arr)
ans += a+b # min값 두 개 더해주고
heapq.heappush(arr, a+b) # 힙에 더한값 새롭게 넣는다 (= 기존 값과 비교가 필요하므로)
print(ans)
솔루션 코드 - 동빈나
- 답은 정해져있었구나...
import heapq
n = int(input())
# 힙(Heap)에 초기 카드 묶음을 모두 삽입
heap = []
for i in range(n):
data = int(input())
heapq.heappush(heap, data)
result = 0
# 힙(Heap)에 원소가 1개 남을 때까지
while len(heap) != 1:
# 가장 작은 2개의 카드 묶음 꺼내기
one = heapq.heappop(heap)
two = heapq.heappop(heap)
# 카드 묶음을 합쳐서 다시 삽입
sum_value = one + two
result += sum_value
heapq.heappush(heap, sum_value)
print(result)
솔루션 코드 - cpp
#include <bits/stdc++.h>
using namespace std;
int n;
int result = 0;
priority_queue <int> heapq;
int main(void) {
cin >> n;
// 힙에 초기 카드 묶음을 모두 삽입
for (int i = 0; i < n; i++) {
int x;
cin >> x;
heapq.push(-x); // 음수 형태로 넣어야 min-heap이 됨
}
// 원소가 1개 남을 때까지
while (heapq.size() != 1) {
int a = -heapq.top();
heapq.pop(); // c++의 pop()은 리턴값이 없음!!
int b = -heapq.top();
heapq.pop();
result += a + b;
heapq.push(-(a + b)); // 음수 형태로 넣어야됨!!
}
cout << result << endl;;
}
- 역시 python보다 훨씬 빠른걸 볼 수 있다.
Do My Best