Coding Test/codility
-
[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 =..
-
[codility] OddOccurrencesInArray c++Coding Test/codility 2022. 4. 8. 16:02
문제 문제 풀이 #include #include #include int solution(std::vector &A) { // write your code in C++14 (g++ 6.2.0) sort(A.begin(), A.end()); for (int i = 0; i < A.size(); i += 2) { if (A[i] != A[i + 1]) { return A[i]; } } return 0; } #define OddOccurrencesInArray #ifdef OddOccurrencesInArray int main() { std::vector A = {9,3,9,3,9,7,9}; std::cout
-
[codility] CyclicRotation c++Coding Test/codility 2022. 4. 8. 15:31
문제 설명 크기가 A.size() 인 배열을 K 만큼 이동하라는 뜻이다. 문제 풀이 #include #include #include #include std::vector solution(std::vector &A, int K) { // write your code in C++14 (g++ 6.2.0) std::vector vecResult(A.size(), 0); for (int i = 0; i < A.size(); i++) { vecResult[(i + K) % A.size()] = A[i]; } return vecResult; } int main() { std::vector ArrayVec = { 3, 8, 9, 7, 6}; int K = 3; std::vector ArrayVec2 = {1,2,3,..
-
[codility] BinaryGap c++Coding Test/codility 2022. 4. 8. 11:39
문제 설명 10진수 N을 2진수로 바꾼 후, 1과 1 사이에 존재하는 0의 개수를 구하는 문제이다. ex, 1001 -> length : 2 1000010001 -> length : 4 , 3 -> 이 때는 더 큰 수를 return 한다 -> 4 10100 -> length : 1 100000 -> length : 0 -> 1이 하나만 있기 때문에 1과 1사이의 0이 없다. 문제 풀이 1. string 에 2진수 변환 저장 2. 1검사해서 index vector에 저장 3. index vector size가 1이라면 1이 한개라는 뜻이므로 return 0 4. index vector 에 1의 index가 저장되어 있기에 각 index에 빼기 연산을 하여 Binary Gap을 구한다. 5. max 함수를 ..