[Lesson 3] PermMissingElem
by 브이담곰
문제
An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A, returns the value of the missing element.
For example, given array A such that:
A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5
the function should return 4, as it is the missing element.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [0..100,000];the elements of A are all distinct;each element of array A is an integer within the range [1..(N + 1)].
풀이
첫번째 시도 score : 80
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
// Implement your solution here
int sum = 0;
int N = A.size() + 1;
for(int i= 0; i < A.size(); i++)
{
sum += A[i];
}
return (N+1)*N/2 - sum;
}
두번째 시도 score : 100
정렬(n*log(n))를 이용하여, 오름차순으로 정렬 한 뒤, index와 비교하여 다르다면 리턴해준다.
만약, 범위가 [1~N+1]일 경우 리스트 A의 길이가 N이라면, for문에서 빠진 요소를 찾아내지 못한다.
마지막에 N+1을 리턴해주는 예외처리를 해줘야 한다.
// you can use includes, for example:
#include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A) {
sort(A.begin(), A.end());
for(int i = 0; i < A.size(); i++)
{
if(A[i] != i + 1) return i+1;
}
return A.size()+1;
}
'Coding Test > Codility' 카테고리의 다른 글
[Lesson 4] FrogRiverOne (0) | 2024.02.21 |
---|---|
[Lesson 3] TapeEquilibrium (0) | 2024.02.21 |
[Lesson 3] FrogJmp (0) | 2024.02.20 |
[Lesson 2] OddOccurrencesInArray (0) | 2024.02.20 |
[Lesson 2] Cycle Rotation (1) | 2024.02.20 |
블로그의 정보
농담곰담곰이의곰담농
브이담곰