[프로그래머스] 야근 지수

---

 이전의 코테에서 상당히 비슷한 문제를 풀었던 기억이 있다. 그때는 왜 그랬는지 모르겠지만, 힙을 사용해야겠다는 생각이 떠오르지 않았었다. 그래도 다행히 코테는 통과했었는데, 면접에서 어떤 식으로 더 최적화할 수 있겠냐는 질문이 듣지 마자 힙이 떠올랐었던 기억이 있다.

 

 제곱의 합을 최소로 만들기 위해서는 가장 모난 놈부터 쳐내면 된다. 가장 모난 놈이라는건 여러 개의 숫자 중에서 가장 큰 놈이다. 반대로 최대로 만들기 위해서는 가장 작은놈부터 하면 될 것 같다. 가장 모난 놈을 쉽게 찾기 위해서는 Max Heap을 사용하면 되는데, 이는 C++ priority_queue라는 STL로 구현되어 있다.

 

 우선 주어진 works 배열의 값들을 다 priorty_queue로 옮겨준다. 그 이후에 가장 큰 놈부터 빼서 -1을 하고 다시 큐에 넣는다. 이 작업을 n번 반복하면 된다. 그 사이에 0이 되어버리는 놈들은 다시 큐에 넣지 않는 예외 처리만 해주면 된다.

 

	#include <string>
	#include <vector>
	#include <queue>
	using namespace std;
	long long solution(int n, vector<int> works) {
	long long answer = 0;
	priority_queue<int> q;
	for (int i = 0; i < works.size(); i++){
	q.push(works[i]);
	}
	while (!q.empty() && n) {
	int cur = q.top(); q.pop();
	if (cur - 1 > 0) {
	q.push(cur - 1);
	}
	n--;
	}
	while(!q.empty()) {
	int cur = q.top(); q.pop();
	answer += cur * cur;
	}
	return answer;
	}

view raw 12927.cpp hosted with ❤ by GitHub

---

지금 준비 중인 코테가 프로그래머스 상에서 보길래 백준 문제를 풀다가 프로그래머스로 넘어왔다. 시험 시간이 2시간인 것으로 보아 난이도가 크게 어렵지는 않을 것 같은데 커트 라인이 높을 것으로 예상된다. 응시 가능 언어 중 Go도 있었다. Go로 문제를 풀면 조금 특이하지 않을까 싶어서 잠깐 고민했다. 하지만 Go를 마지막으로 사용한 지 한 달이 넘었고 일주일 만에 Go로 PS에 익숙해지기는 어렵지 않을까 생각해서 익숙한 C++로 도전하기로 했다.