codility c++
-
[Codility] GenomicRangeQuery c++Coding Test/codility 2022. 8. 11. 15:00
문제 DNA서열은 A, C, G, T 로 구성 되어 있고 1, 2, 3, 4 로 표현된다. string으로 DNA 서열이 주어진다. 배열 P ,Q 의 K번째 값으로 string s의 K(P) ~ K(Q)번째 원소들 중 서열이 제일 먼저인 DNA 인덱스를 저장한다. 문제 해결 2중 for문을 사용하면 시간 복잡도 테스트를 통과하지 못해서 2중 for문을 사용하지 않게 코드를 짜보았다. // you can use includes, for example: #include vector solution(string &S, vector &P, vector &Q) { vector result; for (int i = 0; i < P.size(); i++) { int index = Q[i] - P[i]; string ..
-
[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] 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 함수를 ..