문제 문제 링크 설명 BFS로 풀었다. 공간 절약을 위해 visited 배열을 따로 만들지 않았다. 시작 좌표의 값을 2로 둔다. 다음 칸을 탐색할 때 이전 칸의 값에 1을 더한 값을 저장한다. 도착 지점의 값에 1을 빼준 값이 답이다. while문이 끝날 때 까지 return되지 않았으면 도착할 수 없는 경우이므로, -1을 return한다. 아래는 bfs를 돌렸을 때 maps 배열의 예시이다. [ [ 2, 0, 10, 11, 12 ], [ 3, 0, 9, 0, 11 ], [ 4, 0, 8, 9, 10 ], [ 5, 6, 7, 0, 11 ], [ 0, 0, 0, 0, 12 ] ] 코드 function solution(maps) { let n = maps.length; let m = maps[0].leng..
문제 문제 링크 설명 구현 방법은 다양할 수 있다. 시간복잡도를 고려해야 통과할 수 있다. right - left + 1만큼만 반복문을 돌릴 수 있는 방법을 생각해보자. 틀린 코드 1. 처음부터 끝까지 2차원 배열을 생성하고 2. 1차원 배열로 변환한 후 3. left부터 right까지 slice한다. 하지만 n이 10^7까지 될 수 있어서 역시 이 방법으로는 통과할 수 없었다. function solution(n, left, right) { let answer = []; let arr = []; for(let i = 1; i
문제 문제 링크 설명 문제에서 "구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없다" 라는 조건을 늦게 발견해서 오래걸렸다. people 배열을 정렬한 후, 양쪽 끝을 더해준다. limit를 초과하면 left++만 하고, limit를 초과하지 않으면 left++과 right--를 해준다. 코드 function solution(people, limit) { let answer = 0; let left = 0; let right = people.length - 1; people.sort((a, b) => b - a); while (left
문제 문제 링크 설명 cache hit일때, 삽입정렬을 응용해서 풀었다. 코드 function solution(cacheSize, cities) { const CACHE_HIT_TIME = 1; const CACHE_MISS_TIME = 5; let cache = Array.from({ length: cacheSize }); let total = 0; for (let city of cities) { city = city.toLowerCase(); let idx = cache.indexOf(city); if (idx !== -1) { // cache hit for (j = idx - 1; j > -1; j--) { cache[j + 1] = cache[j]; } cache[0] = city; total +..
문제 문제 링크 설명 원래는 힙 2개를 사용해서 푸는 문제이다. 하지만 프로그래머스에서는 배열 1개로 풀어도 통과된다 다음에는 힙을 직접 구현해서 풀어보고싶다. 코드 function solution(operations) { let queue = []; for(let operation of operations){ if (operation ==='D 1'){ let max = Math.max(...queue); let deleted = false; let newQueue = []; for(let q of queue){ if(q===max){ if(!deleted){ deleted = true; } }else{ newQueue.push(q); } } queue = newQueue; } else if(opera..
문제 문제 링크 설명 반복문을 돌면서 단어를 집합에 넣는다. 이미 집합에 있는 단어이거나 이전 단어의 끝 문자와 현재 단어의 첫 문자가 다르면 계산해서 반환한다. 반복문을 다 돌았다면 [0, 0]을 반환한다. 코드 function solution(n, words) { let s = new Set(); s.add(words[0]); for (let i = 1; i < words.length; i++) { let prev = words[i - 1]; let curr = words[i]; if (s.has(curr) || prev.at(-1) !== curr.at(0)) { return [(i % n) + 1, parseInt(i / n) + 1]; } else s.add(curr); } return [0, ..
문제 문제 링크 설명 Stack을 활용해서 풀었다. 풀이 function solution(s) { let stack = [s[0]]; for (let i = 1; i < s.length; i++) { let c = s[i]; if (stack.at(-1) === c) stack.pop(); else stack.push(c); } return stack.length === 0 ? 1 : 0; }
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설명 수학적 지식으로 푼 분들도 계셨다. 나는 백준 2003번 수들의 합 2 문제처럼 투포인터 방식을 응용해서 풀었다. 코드 function solution(n) { let sum = 0; let answer = 0; let left = 1; for (let right = 1; right n) { while (sum > n) { sum -= left; left++; if (sum === n) answer++; } } } return answer; }
