문제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/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/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/valid-palindrome/?envType=study-plan-v2&envId=top-interview-150 풀이이번 문제는 투 포인터 알고리즘을 이용한 팬린드롬 확인 문제이다.펜린드롬이란?거꾸로 읽어도 원문과 똑같은 문자열이나 수열을 의미한다.EX) 기러기 0123210 등등 정규 표현식을 활용해 두 가지 방법으로 풀이를 진행해 봤다.정규 표현을 이용해 입력된 문자열에서 숫자와 영문자(소대문자)를 제외한 나머지를 제거하고 소문자로 변환. 이후에 두 개의 포인터 변수를 활용해 각 문자를 비교하며 풀이두 개의 포인터를 선언하고 문자열의 맨 앞과 맨 뒤에서 부터 영문자나 숫자가 나올때 까지 포인터를 이동.이후, 문자열을 소문자로 변환한 뒤 두 개..
문제https://leetcode.com/problems/merge-sorted-array/submissions/1658165264/?envType=study-plan-v2&envId=top-interview-150풀이이번 문제는 두 개의 배열을 정렬하여 합치는 문제이다. 이 문제를 두 가지 방법으로 풀어봤다.spread 연산자를 이용해 하나의 배열로 만든다음 정렬두 개의 배열에 두 개의 포인터를 적용해(투 포인터 알고리즘) 크기를 비교하며 정렬 코드 1/** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modif..
문제https://www.acmicpc.net/problem/2003 풀이투포인터의 기본 문제이며, 주어지는 수열에서 연속된 수들의 합이 M이 되면 카운트를 올리는 문제이다. 이 문제에서 while 문을 이용해 반복해주는 부분이 있는데, 이 while 문의 조건에 원래는 lp 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');const [n, m] = input.shift().split(' ').map(Number);const arr = input[0].split(' ').map(Num..
