728x90
codility PermMissingElem
-
[codility] PermMissingElem c++Coding Test/codility 2022. 4. 9. 18:26
문제 주어진 배열의 원소 중에 연속된 (+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 #include #include #include int solution(std::vector &A) { long len = A.size() + 1; long nSum =..