Algorithm
-
[프로그래머스] 짝지어 제거하기Algorithm/자료구조 2021. 9. 30. 12:40
문제 : https://programmers.co.kr/learn/courses/30/lessons/12973?language=javascript 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr - s의 길이는 최대 1,000,000이다. 즉 O(NlogN) 이하로 처리해야 한다. - 문자열 문제에서 이정도의 길이제한이 주어진다면, 이중 for문 이상의 알고리즘을 구현하지 못하므로 스택/큐를 고민해야한다. function solution(s) { let stack = [] for(let char ..
-
[프로그래머스] 문자열 압축Algorithm/문자열 2021. 9. 20. 16:06
문제 링크 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr - s의 길이는 1000 이하이다. 즉 O(n^2) 정도의 알고리즘으로 풀 수 있다. - 문자열을 활용한 단순 구현 문제인 것 같다. 카카오 코테 1번인가 2번이었던걸로 기억한다. function solution(s) { if(s.length === 1) return 1 let answerArr = [] for(let i = 1; i 1? compressedString + cnt + tempSubStr : compressedString + te..
-
[Codility - Counting Elements] BracketsAlgorithm/자료구조 2021. 9. 20. 13:34
문제 링크 NumberOfDiscIntersections coding task - Learn to Code - Codility Compute the number of intersections in a sequence of discs. app.codility.com - 스택 문제중에서도 가장 쉬운 문제인 것 같다. 백준 브론즈 냄새가.. - 자바스크립트는 C++처럼 stack STL을 제공하지 않지만, array를 잘 활용하면 stack과 queue를 사용할 수 있다. - N은 200,000 이하의 양의 정수이다. 따라서, O(NlogN) 이하의 알고리즘을 구현해야 하고, 0일때 예외 처리를 해 주어야 한다. function solution(S) { if(S.length === 0) return 1; le..
-
[Codility - Counting Elements] TriangleAlgorithm/Sort 2021. 9. 20. 13:08
문제 링크 Triangle coding task - Learn to Code - Codility Determine whether a triangle can be built from a given set of edges. app.codility.com - N은 100,000 이하의 수이다. 따라서, O(NlogN)이하의 알고리즘을 구현해야 한다. function solution(A) { const positiveArray = A.filter((elem)=>elem > 0).sort((a,b)=>a-b) for(let i = 0; i positiveArray[i+2]) retur..
-
[Codility - Counting Elements] MaxProductOfThreeAlgorithm/구현(Brute force, Back tracking, etc.) 2021. 9. 19. 14:28
문제 링크 MaxProductOfThree coding task - Learn to Code - Codility Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R). app.codility.com - N 은 3 이상 100,000 이하이다. 따라서, 최악의 경우 모든 triplet의 경우의 수는 99998*99997*99996 이므로 당연히 시간초과가 난다. 따라서 다른 방법을 사용해야 한다. function solution(A) { A.sort((a,b)=>a-b) let answer = A[A.length-1]*A[A.length-2]*A[A.length-3] answer = Math.max(A[0]*A[1]*A[A.length-1], answer) ret..
-
[Codility - Counting Elements] GenomicRangeQueryAlgorithm/구현(Brute force, Back tracking, etc.) 2021. 9. 19. 13:44
https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/ GenomicRangeQuery coding task - Learn to Code - Codility Find the minimal nucleotide from a range of sequence DNA. app.codility.com - N은 100,000이하, M은 50,000 이하이다. 따라서, O(MN)등의 시간복잡도가 나오면 시간 초과가 난다. - 처음엔 부분 문자열을 추출한 후 binarySearch를 쓸 생각이었는데, 이걸 위해선 먼저 오름차순 정렬을 해야하므로, 그 과정의 시간복잡도가 O(NlogN)이 되버리기 때문에 불가능하다고 판단했다. func..
-
[Codility - Counting Elements] CountDivAlgorithm/구현(Brute force, Back tracking, etc.) 2021. 9. 19. 13:03
https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/ CountDiv coding task - Learn to Code - Codility Compute number of integers divisible by k in range [a..b]. app.codility.com - A,B은 20억 이하의 양의 정수이다. 즉, 곱셈이나 나눗셈이 들어갈 것이다. - 예외처리를 잘 해주어야 한다. function solution(A, B, K) { let cnt = parseInt(B / K) - parseInt(A / K); if(A % K === 0) cnt += 1; return cnt; } - (0부터 B까지 나누어 떨어지는수) - (..
-
[Codility - Counting Elements] MissingIntegerAlgorithm/구현(Brute force, Back tracking, etc.) 2021. 9. 19. 12:24
https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/ MissingInteger coding task - Learn to Code - Codility Find the smallest positive integer that does not occur in a given sequence. app.codility.com - N의 제한은 200,000이다. O(NlogN) 이하의 알고리즘을 이용해서 풀어야 한다. function solution(A) { const set = new Set(A) const tempSortedArr = [...set].filter(elem=> elem > 0).sort((a,b)=>a-b)..