[codility] PermMissingElem c++

• 문제

주어진 배열의 원소 중에 연속된 (+1) 수가 아닌 값을 찾는 문제입니다.

범위는 1~(N+1) 입니다. 원소는 +1 만큼 증가한다고 합니다. 

• 문제 풀이

처음에는 간단하게 배열의 크기만큼 반복문으로 구하려고 했는데 50%가 나왔다. 

이렇게 풀면 안된다. N+1개 만큼 반복하기 때문에 시간이 오래걸리는 연산이다.

1. 1부터 1씩 증가하는 N+1 개의 원소들의 합을 구하는 수열 공식을 이용해야 한다.

-> (N+1)(N+2) / 2;

2. A배열 원소의 합과 1~N+1의 합을 빼면 A배열에 빠진 원소를 구할 수 있다.

 

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

#include <iostream>


int solution(std::vector<int> &A) {

	long len = A.size() + 1;
	long nSum = (len * (len + 1)) / 2;
	long count = 0;

	for (const auto &it : A) {
		count += it;
	}

	int result = (nSum - count);
	   
	return result;

}

#define PermMissingElem

#ifdef PermMissingElem

int main() {

	std::vector<int> nVec = { 2,3,1,5 };
	std::cout << solution(nVec);

	return 0;
}
#endif