그냥 코드 최적화되는게 맘에 들어서 글을 작성해보았습니다.
스터디원의 코드를 보다가 깔끔해서 배운 기념 🙌
🔗 문제
https://www.acmicpc.net/problem/13975
✏️ 풀이
문제를 요약하자면, N개의 파일이 있고, 두 파일을 합치는 비용을 최소로 하는 방법을 고안하는거다.
나의 접근법은 오름차순 우선순위 큐를 이용하는 것이다.
합쳐진 파일 또한 모든 파일이 1개가 될 때까지 사용을 해야해서 pq에 넣어야 한다.
컨테이너의 삽입, 삭제가 빈번하게 일어나는 동시에 정렬이 필요하기 때문에 pq를 선택했다.
주의할 점은 데이터 타입이다.
- 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 1,000,000)
- 파일의 크기는 10,000을 초과하지 않는다
10000 = 10^4 크기가 만약에 10^6개 있어서 sum이 점점 커진다면? int형으로 감당이 안되기 때문에 long long으로 지정해주자.
코드 최적화
파일을 하나씩 빼면서 pq에서 2개의 값만 쓴다는 것이 직관적으로 보인다는 장점이 있다.
while(!pq.empty())
{
sum += pq.top();
pq.pop();
if(++cnt == 2)
{
answer += sum;
pq.push(sum);
sum = 0;
cnt = 0;
}
}
그렇지만 두개씩 빼면 코드가 더 깔끔하다.
while문의 조건 2개 이상일 때로 수정해야 하지만, cnt 조건문이 없어져서 훨씬 보기 좋다.
while(pq.size() >= 2)
{
sum = pq.top(); pq.pop();
sum += pq.top(); pq.pop();
answer += sum;
pq.push(sum);
}
💾 소스
#include <iostream>
#include <queue>
typedef std::priority_queue<long long> PQ;
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
long long T, N, answer, sum, input;
std::cin >> T;
while (T--)
{
PQ pq;
answer = 0;
std::cin >> N;
for(int i=0; i<N; ++i)
{
std::cin >> input;
pq.push(input*-1);
}
while(pq.size() >= 2)
{
sum = pq.top(); pq.pop();
sum += pq.top(); pq.pop();
answer += sum;
pq.push(sum);
}
std::cout << answer *-1<<"\\n";
}// T
} // main