본문 바로가기

분류 전체보기138

[프로그래머스] 뉴스 클러스터링 (javascript) 주어진 두개의 문자열에 대해 자카드 유사도를 리턴하는 문제이다. 자카드 유사도란 문자열을 2개씩 나누어 쪼개고 france => fr, ra, an, nc, ce, french => fr, re, en, nc, ch 합집합과 교집합의 원소 갯수를 구해 나눈 것이다. insersection => {fr, nc} union => {fr, ra, an, nc, ce, re, en, ch} 2/8 = 0.25 유의할 점이 있는데 1. 여기서 합집합과 교집합을 구할 때, 중복을 허용하는 집합이라는 점에 유의해야 한다. 예를들어 aaaa, aaa가 주어졌다면 => [aa, aa, aa] [aa, aa] 중복을 허용하지 않는다면 교집합은 [aa]가 되겠지만, 이 문제의 경우 중복을 허용하기 때문에 [aa, aa]가 .. 2021. 8. 12.
[토비의 스프링] 오브젝트와 의존관계 보호되어 있는 글 입니다. 2021. 7. 23.
[LeetCode] Minimum Path Sum (javascript) 좌상단에서 출발하여 우하단까지 오른쪽, 아래로만 움직여 도착해야 한다. 가는 경로의 숫자를 모두 더했을때, 가장 작은 숫자를 구하는 문제다. 최단경로 경우의 수 문제와 유사하게 풀 수 있다. 처음엔 모든 경로를 처음부터 더해가면서 최솟값을 구해보려고 했으나.. (첫번째 경로 결과 : 10, 두번째 경로 결과 : 8 ...) Time Limit에 걸렸다. 이미 구해놓은 결과값보다 큰 경우 패스하도록 해도 마찬가지... 더보기 틀린 풀이 // 잘못된 접근방식(Time Limit) var minPathSum = function (grid) { let result = Infinity; const ml = grid.length - 1; const nl = grid[0].length -1; console.log(m.. 2021. 6. 22.
[LeetCode] Merge Intervals (javascript) 주어진 2차배열 내의 요소들끼리 겹치는 것을 합쳐주는 문제다. 예를들어 [[1, 3], [2, 4], [5, 8]] 이 있다고 하면 이렇게 [[1, 4], [5, 8]]로 겹치는 요소는 합쳐주는 것이다. 여기서 각 요소의 첫 번째 요소([1, 4]의 1)를 head, 두 번째 요소([1, 4]의 4)를 tail이라고 부르겠다. 그래서 배열을 차례대로 돌면서, 현재 요소와 다음 요소가 겹치는 부분이 있으면 합치는 방식으로 풀었다. 어렵지 않게 풀리는듯 했으나 간과했던 포인트가 있었는데, 1. 주어진 배열들은 소팅되어 있지 않다. 즉, 차례대로 합치다간 나중에 제외되는 요소가 나타난다. ex. [[1, 3], [2, 4], [5, 8], [2, 3]] => [[1, 4], [5, 8]]이 되어야 하나 [[1.. 2021. 6. 15.
[LeetCode] Unique Paths, Unique Paths II (javascript) Unique Path 전형적인 최단경로 찾기 조합 문제! (m + n)! / m! * n! 식을 이용하여 풀었다. /** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths = function(m, n) { // (m+n-2)! / ((m-1)! * (n-1)!) console.log(factorial(m+n-2), factorial(m-1), factorial(n-1)) return factorial(m+n-2)/(factorial(m-1)*factorial(n-1)); }; const factorial = (n) => { if(n == 0) return 1; let num = n; for (let i = num -.. 2021. 6. 15.
[LeetCode] Longest Substring Without Repeating Characters (javascript) 가장 긴 반복되지 않는 문자열의 길이를 리턴하는 문제다. 예를들어 abcdaddd => [abcd][ad][d][d] = 4 abcabc => [abc][abc] = 3 처음엔 문자별로 for문을 돌면서 다음에 출현하는 같은 문자까지의 index 차이를 구하려고 했다. abcabc => [abc] "a"bc => 3 다만 이런경우... abbabc => [abb] "a"bc => 3 이런 케이스를 피할 수 없고, 또 abb안에서 중복이 없는지 검사하는 등 복잡해지게 된다. 다른 풀이들을 참고한 결과, substring해가면서 중복이 없으면 결과값에 더해주고, 중복이 있으면 앞글자를 방출하는 형태가 가장 이해하기도 편하고 코드도 깔끔해 보여서 이렇게 구현했다. /** * @param {string} s *.. 2021. 6. 15.
[LeetCode] Longest Substring Without Repeating Characters (javascript) 반복되지 않는 가장 긴 문자열의 길이를 찾는 문제다. 예를들어 abcabcda 라면, abcd or bcda = 4가 된다. current라는 문자열 변수를 두고 현재 문자열에 포함되지 않은 문자라면 더해가면 되고, 포함되어 있다면 잘라내면 된다. current = "abc" 인 상태에서 다음 a가 들어오게 되면 current에 존재하는 a의 index를 찾아 그 다음부터 잘라내고, current.substring(2), current = "bc" 다음으로 들어온 a를 더해준다. current += "a", current = "bcd" /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function (s) { if .. 2021. 6. 11.
[LeetCode] Repeated String Match (javascript) 주어진 문자열 a, b가 있을 때, a를 몇번 반복해야 b가 한번이라도 포함되는지 찾는 문제다. 처음엔 별생각 없이 str.includes(b) 대신 new RegExp(b).test(str) 를 사용해 풀었었다. 그러나 정규식보다 includes가 훨씬 빨랐다. // 정규식보다 includes를 쓰는게 런타임도, 메모리도 훨씬 낫다 // 정규식 : Runtime 340ms, Memory 45MB // includes : Runtime 84ms, Memory 40.4MB /** * @param {string} a * @param {string} b * @return {number} */ var repeatedStringMatch = function(a, b) { let str = a; let count .. 2021. 6. 11.
[LeetCode] Single Number (javascript) 주어진 배열에서 하나만 존재하는 숫자를 찾아 리턴하는 문제다. 배열에서 숫자를 하나씩 꺼내가면서, 남은 배열에 같은 숫자가 존재하지 않는 경우 리턴한다. 존재하는 경우, splice로 확인한 숫자를 제거한다. /** * @param {number[]} nums * @return {number} */ var singleNumber = function(nums) { const count = Math.floor(nums.length/2); for(let i = 0; i n===item); if(index > -1) { nums.splice(index, 1); } else {.. 2021. 6. 11.

티스토리툴바