[프로그래머스] (C++) 야근지수

문제

• 링크

코딩테스트 연습 - 야근 지수 | 프로그래머스

생각해볼만한 점

• 가장 큰 works의 값부터 1 씩 줄여가면 되지 않을까?
• 결국 가장 작은 값 (최소화한 값) 이란 제곱하는 베이스가 평균적으로 가장 작게 나오는 값이지 않을까? 왜냐하면 베이스의 1 차이가 큰 값일 수록 더 확연하기 때문이다 (예. 4에서 3으로 만드는 것이 3에서 2 만드는 것보다 훨씬 줄어드는 수가 크다).

소스 코드 (1차 시도)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution(int n, vector<int> works) {
	std::sort(works.begin(), works.end(), greater<int>());
	vector<int>::iterator iter = works.begin();
	while (n > 0) {
		if ((iter+1 == works.end()) && (*iter > 0)) {
			*iter -= 1;
			n--;
			iter = works.begin();
		} else if (*iter > (*(iter+1)) && (*iter > 0)) {
			*iter -= 1;
			n--;
			iter = works.begin();
		} else if ((*iter == 0) && (iter + 1 == works.end())) {
			break;
		} else {
			iter++;
		}
	}
	long long answer = 0;
	for (iter = works.begin(); iter != works.end(); iter++) {
		answer += ((*iter) * (*iter));
	}
	return answer;
}

채점 결과 (1차 시도)

정확성: 86.7

효율성: 0.0

합계: 86.7 / 100.0

 

효율성 실패 원인 가능성

• works 를 1 낮추고 다시 begin으로 돌아가는 것
  • begin으로 돌아갈 이유 없이 바로 앞 수를 1 낮추면 된다.

소스 코드 (2차 시도)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution(int n, vector<int> works) {
	std::sort(works.begin(), works.end(), greater<int>());
	vector<int>::iterator iter = works.begin();
	while (n > 0) {
		if ((iter+1 == works.end()) && (*iter > 0)) {
			*iter -= 1;
			n--;
			if (iter != works.begin()) iter--;
		} else if (*iter > (*(iter+1)) && (*iter > 0)) {
			*iter -= 1;
			n--;
			if (iter != works.begin()) iter--;
		} else if ((*iter == 0) && (iter + 1 == works.end())) {
			break;
		} else {
			iter++;
		}
	}
	long long answer = 0;
	for (iter = works.begin(); iter != works.end(); iter++) {
		answer += ((*iter) * (*iter));
	}
	return answer;
}

채점 결과 (2차 시도)

정확성: 86.7

효율성: 13.3

합계: 100.0 / 100.0