Algorithm/문제풀이 Codility Lesson7 - Brackets 🔍 문제 Brackets coding task - Learn to Code - Codility Determine whether a given string of parentheses (multiple types) is properly nested. app.codility.com ✏️ 풀이 - JS 문자열안에 괄호의 짝이 알맞게 들어가있는지 체크하는 문제이다. 기본적으로 stack의 후입선출을 이용해서 풀었다. 여는 괄호는 따로 arr이라는 배열에 넣어주고, 닫는 괄호가 나왔을 때는 앞에서 여는 괄호가 담긴 arr.pop()을 해서 가장 마지막의 여는 괄호를 꺼내서 맞는 짝인지 확인해주었다. 참고로, 처음에는 여는 괄호의 짝이 없는(닫는 괄호가 부족한 상황) 예외를 생각하지 못해서 조금 해멨다. if(arr.. 더보기 Codility Lesson6 - NumberOfDiscIntersections 🔍 문제 NumberOfDiscIntersections coding task - Learn to Code - Codility Compute the number of intersections in a sequence of discs. app.codility.com ✏️ 풀이 - JS 처음 주어진 배열 A로 원을 그린다. 배열 인덱스가 중심점, 반지름은 배열의 값이다. 원을 그렸을 때 겹치는 원의 개수를 구하면 된다. 이번에도 역시나 나는 이중 for문에서 헤어나오지 못했다... 아래와 같이 풀어서 정확도는 100%지만 역시나 performance에서는 62%가 나와서 총 81%가 나왔다. 시간복잡도는 N(N**2)😓 일단 논리는 처음 배열 A에서 index를 기준으로 원 그리기의 startPoint와 en.. 더보기 Codility Lesson6 - Triangle 🔍 문제 Triangle coding task - Learn to Code - Codility Determine whether a triangle can be built from a given set of edges. app.codility.com ✏️ 풀이 - JS 배열의 원소중 삼각형을 만들 수 있는 조합이 있는지 묻는 문제이다. 삼각형을 만들기 위해서는 세 변이 있을 때, 가장 큰 변을 제외한 나머지 두 변의 합이 가장 큰 변보다 커야한다. 배열 A를 오름차순으로 정렬한 후 for문을 돌면서 차례대로 3가지 조합을 만들어주면서 1번째, 2번째 숫자를 합한 값이 3번째 숫자보다 큰지 확인해 주면 된다. 시간 복잡도는 O(N*log(N)) 이고 정확도, 효율성 모두 100%로 통과하였다. functio.. 더보기 Codility Lesson6 - Distinct 🔍 문제 Distinct coding task - Learn to Code - Codility Compute number of distinct values in an array. app.codility.com ✏️ 풀이 - JS 배열 A에서 순수 값(중복X)이 총 몇 개인지 구하는 문제이다. 먼저 배열을 오름차순으로 정렬한다. 그리고나서 current 변수에 현재 보고있는 값을 넣어주고, current와 값이 다른 값이 나왔다면 cnt(최종 return할 값)에 +1을 해주고, current값도 달라진 값으로 변경해준다. 그렇게 배열을 순회해가면서 값의 갯수를 찾아준다. 시간 복잡도는 O(N*log(N)) of O(N), 정확도와 효율성 모두 100%가 나왔다. function solution(A) { .. 더보기 Codility Lesson6 - MaxProductOfThree 🔍 문제 MaxProductOfThree coding task - Learn to Code - Codility Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R). app.codility.com ✏️ 풀이 - JS 배열의 3 원소를 곱해서 가장 큰 수가 나오는 값을 return 해주면 된다. 먼저, 배열 A를 오름 차순으로 정렬해준다. 만약 배열의 모든 수가 음수나 양수라면, 아래 코드에서는 n이 최대 값이 된다. 이 때, 함정이 음수와 양수가 함께 있을 경우이다. 음수는 절대값이 클 수록 왼쪽으로 정렬되기 때문에 절대값이 큰 A[0] * A[1]을 해서 두 음수를 곱해 양수가 되는 경우를 생각해주고, 마지막으로 가장 큰 수 A[A.length]를 곱해준다. .. 더보기 Codility Lesson5 - CountDiv 🔍 문제 CountDiv coding task - Learn to Code - Codility Compute number of integers divisible by k in range [a..b]. app.codility.com ✏️ 풀이 - JS 일단 문제 자체는 쉽다. 주어진 범위내에서 어떤 정수 값으로 나누어 떨어지는 수의 개수를 구하면 되는 문제다. 단순하게 생각하면 아래와 같이 풀면되지만, 문제에서 가장 중요한건 효율적으로 풀어야 하기 때문에 performance면에서 0%이다. function solution(A, B, K) { let cnt = 0; for(let i = A; i 더보기 Codility Lesson5 - MinAvgTwoSlice 🔍 문제 MinAvgTwoSlice coding task - Learn to Code - Codility Find the minimal average of any slice containing at least two elements. app.codility.com ✏️ 풀이 - JS 아무리 생각해도 이중 for문으로 배열을 일일히 순회하면서 값을 찾는 방법 밖에는 떠오르지 않는다. 왜 나는 항상 for문으로 푸는게 가장 먼저 생각나는 걸까... 후... 하지만 timeout error가 나올 것이 뻔하므로 다른 방법을 떠올리려 했지만 아무리 생각해도 떠오르지가 않아 구글 선생님의 도움을 받아 풀어보았다. 문제는 아래를 참고해서 풀면된다. 검색 안했으면 아마 풀지 못했을 것 같다. 하나 배웠다 😎 크크 어.. 더보기 Codility Lesson5 - GenomicRangeQuery 🔍 문제 GenomicRangeQuery coding task - Learn to Code - Codility Find the minimal nucleotide from a range of sequence DNA. app.codility.com ✏️ 풀이 - JS function solution(S, P, Q) { let resultArr = []; for(let i = 0; i < P.length; i++) { // slice메소드는 두 번째 index까지는 포함시키지 않으므로 포함해서 자를수있도록 +1 해줌 let temp = S.slice(P[i], Q[i]+1); if(temp.indexOf('A') !== -1) { resultArr.push(1); } else if (temp.indexOf('.. 더보기 Codility Lesson5 - PassingCars 🔍 문제 PassingCars coding task - Learn to Code - Codility Count the number of passing cars on the road. app.codility.com ✏️ 풀이 - JS function solution(A) { const pArr = []; //0인 A의 idx배열 const qArr = []; //1인 A의 idx배열 let carCnt = 0; for(let i in A) { if(A[i] === 1) { qArr.push(i); } else { pArr.push(i); } } //짝이 없는경우 if(pArr.length === 0 || qArr.length === 0) { return carCnt; } for(let i in pArr) .. 더보기 Codility Lesson4 - MissingInteger 🔍 문제 MissingInteger coding task - Learn to Code - Codility Find the smallest positive integer that does not occur in a given sequence. app.codility.com ✏️ 풀이 - JS function solution(A) { if(Array.isArray(A)) { let missingNum; for(let i = 1; i < 100000; i++) { if(A.indexOf(i) === -1) { return missingNum = i; } } } } 일단은 생각나는대로 정수 1부터 시작해서 배열이 가지고 있는지, 아닌지 일일히 비교하는 방식을 써보았다. 시간 복잡도가 O(N**2)가 나왔고, 정.. 더보기 이전 1 2 3 4 5 다음