Coding Test
-
[codility] MaxCounters c++Coding Test/codility 2022. 4. 10. 10:01
문제 문제 풀이 #include #include #include int solution(std::vector &A) { sort(A.begin(), A.end()); int index = A.size() - 1; if (A.at(index) < 0) return 1; int min = 1; for (int i = 0; i < index + 1; i++) { if (min == A[i]) min++; } return min; } #define MaxCounters #ifdef MaxCounters int main() { std::vector nVec = { 1,3,6,4,1,2}; std::cout
-
[codility] MaxCounters c++Coding Test/codility 2022. 4. 10. 09:21
문제 배열 A가 주어진다. A의 원소들은 +1 count 되는 배열의 인덱스를 의미한다. A[0] = 3 -> (0, 0, 1, 0, 0) : 3번째 자리 +1 A[1] = 4 -> (0, 0, 1, 1, 0) : 4번째 자리 +1 A[2] = 4 -> (0, 0, 1, 2, 0) : 4번째 자리 +1 -> 여기서 max count 발생 A[3] = 6 -> (2, 2, 2, 2, 2) : max counters = 6 -> 모든 원소 값을 원소의 최댓값인 2로 설정 A[4] = 1 -> (3, 2, 2, 2, 2) : 1번째 자리 +1 A[5] = 4 -> (3, 2, 2, 3, 2) : 4번째 자리 +1 A[6] = 4 -> (3, 2, 2, 4, 2) : 4번째 자리 +1 최종 return 값 = ..
-
[codility] PermCheck c++Coding Test/codility 2022. 4. 9. 21:32
문제 permutation(순열) 인지 체크하는 문제이다. 문제 해결 처음에 생각한 풀이는 75%가 나왔다. 1. A배열의 합 구하기 2. A배열의 크기로 A.size() 일 때 순열의 합 구하기 3. 1,2 비교하기 #include #include #include #include #include int solution3(std::vector &A) { int len = A.size()+1; long sumP = len * (len + 1) / 2; long sumA = std::accumulate(A.begin(), A.end(), 0); if (sumP != sumA) return 0; return 1; } #define PermCheck #ifdef PermCheck int main() { std:..
-
[codility] FrogRiverOne c++Coding Test/codility 2022. 4. 9. 21:08
문제 개구리가 가장 빨리 강을 건널 수 있는 나뭇잎의 위치?의 인덱스 값을 구하는 문제같다. A배열의 인덱스인 K는 시간(초)를 의미한다고 한다. 문제 해결 1. set 자료구조를 사용한다. set은 중복을 허용하지 않고, 자동으로 오름차순으로 정렬되는 특징이 있다. set 변수의 크기가 X와 같다면 목적지X에 도달한 것이다. #include #include #include #include #include int solution(int X, std::vector &A){ int len = A.size(); std::set nSet; for (int i = 0; i < len; i++) { nSet.insert(A.at(i)); if (nSet.size() == X) return i; } return -1..
-
[codility] TapeEquilibrium c++Coding Test/codility 2022. 4. 9. 19:06
문제 |(A[1] + ... + A[P-1] ) - (A[P] + ... +A[N])| 을 구하는 문제이다. 즉, A배열의 0~(P-1)번 까지 합 - 나머지 원소의 합의 절댓값을 구한다. P 값에 따른 절댓값 중 최솟값을 구하는 문제이다. P의 범위 : (0 < P < N) 문제 해결 #include #include #include #include #include int solution2(std::vector &A) { long end = std::accumulate(A.begin(), A.end(), 0); long len = A.size(); long front =0; int minimum = INT8_MAX; for (int i = 0; i < len - 1; i++) { front += A.at..
-
[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