문제https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-interview-150 풀이이번 문제는 투 포인터 알고리즘 문제이며, 두 가지 방법을 적용해봤다. 첫 번째 풀이는 O(n^2) 시간 복잡도를 갖는 방법이였다. 사실 투 포인터라 보기 애매한 탐색 로직을 적용한 방법이며, 테스트 케이스는 통과했지만, 히든 케이스에서 시간초과가 발생했다. 두 번재 풀이는 O(n) 시간 복잡도를 갖는 방법이며, 이는 문제의 특성을 잘 파악하는 것이 중요하다. 넓이를 구할 때 왼쪽 오른쪽 어느 한쪽 봉의 길이가 다른 쪽의 길이보다 길때 포인터를 이동시키며 탐색하며 탐색할 수 있다. 코드/** *..
코딩 테스트
문제https://leetcode.com/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150 풀이해당 문제는 두 가지 방식으로 풀이해봤다.하나는 각 칸마다 도달할 수 있는 경우를 기록하는 방법, 또 다른 방법은 마지막 인덱스 부터 도달할 수 있는지 검증하는 방법이다. 코드/** * @param {number[]} nums * @return {boolean} */// 첫 번째 코드// var canJump = function(nums) {// if(nums.length === 1) return true;// const lastIdx = nums.length - 1;// const test = Array.from({len..
문제https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150 풀이투 포인터를 이용한 문제이다. 내가 해맸던 부분은 두 개의 포인터의 시작 위치를 잘못 지정했었다.처음에는 0, 1 번 인덱스로 포인터를 지정하고 시작했다. 이런 환경에서 투 포인터 형식으로 시작하면 제대로된 크기 비교를 하기 힘들다고 느꼈다. 예를 들어 [1, 3, 5, 24, 64, 102] 에서 타깃이 67이라고 가정한다면 내가 작성한 로직에서는 경우의 수를 탐색하기에 많은 조건문이 필요해지고 복잡해진다고 생각했다. 이런 문제를 해결하기 위해 포인터의 위치를 양 끝으로 옮겨 타깃보다 크다면 오른쪽 포..
문제https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150 풀이해당 문제는 아래의 사진을 참고하며 설명해보자. Set 객체에 값을 넣어주며 중복 처리를 진행한다. 만약 중복된 문자열이 나온다면 왼쪽 포인터를 옮기며 탐색을 진행한다. 코드/** * @param {string} s * @return {number} */// 첫 번째 풀이// var lengthOfLongestSubstring = function(s) {// if(s.length === 0) return 0;// let answer = 0;/..
문제https://leetcode.com/problems/is-subsequence/?envType=study-plan-v2&envId=top-interview-150 코드// /**// * @param {string} s// * @param {string} t// * @return {boolean}// */// var isSubsequence = function(s, t) {// let [sp, tp] = [0, 0];// while(tp
문제https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150풀이이 문제는 나름 쉬운 문제이다. i 번째의 수가 val 값과 같다면 배열에서 제거해주는 문제이다. 단순히 pop을 해도 괜찬으나 필자는 스왑 동작을 통해 문제를 풀어봤다. 코드/** * @param {number[]} nums * @param {number} val * @return {number} */var removeElement = function(nums, val) { let cnt = 0; let [lp, rp] = [0, nums.length - 1]; for(let num of nums){ if(..
