코딩곳간

문제 링크 분류 / 레벨 / 언어탐욕법(Greedy) / LV.1 / Javscript 설명평범하게 한번만 루프를 돌면 될 것 같은 문제인데,문제에서 여분을 가져온 사람이 도난을 당하면 그 경우를 최우선으로 처리한다고 명시해놓았다.그래서 루프를 2번 돌아야한다. lost와 reserve에서 같은 요소가 있다면 둘 다 빼는 루프 lost 요소 - 1 == reserve 요소orlost 요소 + 1 == reserve 요소인 경우, lost와 reserve에서 각 요소 제거 전체 코드12345678910111213141516171819202122232425262728function solution(n, lost, reserve) { lost = lost.reduce((acc, cur) => { const a = reserve.indexOf(cur); if (a > -1) ...

문제 링크 분류 / 레벨 / 언어정렬 / LV.2 / Javscript 설명큰 순서대로 정렬한 후,i를 올려가며 h인덱스의 조건을 만족하는지 검증한다.h이상의 요소를 따로 count할 필요가 없는데그 이유는, i를 1씩 올리는 것 자체가 count를 담고 있기 때문이다. 전체 코드12345678function solution(citations) { const sorted = citations.filter(a => a > 0).sort((a, b) => b - a); let i = 0; for (i = 0; i < sorted.length; i++) { if (i + 1 >= sorted[i]) break; } return i;}

문제 링크 분류 / 레벨 / 언어스택,큐 / LV.2 / Javscript 설명어떤 것을 만들어서 => 어떤 순서로 => 어떤 기준으로처리할지만 생각하면 된다.배열과 조건문만 알아도 풀 수 있다. JS array의 내장함수 map과 reduce를 사용! 전체 코드12345678910111213let days = 0;function solution(progresses, speeds) { return progresses .map((progress, i) => Math.ceil((100 - progress) / speeds[i])) .reduce((acc, curr) => { if (curr > days) { days = curr; acc.push(1); } else acc[acc.length - 1] += 1; ...

문제 링크 분류 / 레벨 / 언어DFS,BFS / LV.3 / Javscript 설명DFS 풀이스택을 쓰거나 재귀함수로 푸는 방법 2개가 있다.이 문제는 재귀함수를 사용하여 풀었다.재귀함수는 재귀 탈출을 확실히 정의 할 수 있을 때 사용해야 한다. BFS 풀이큐를 사용한다.BFS는 각 depth가 기준이 되어 형제 노드를 우선으로 탐색한다.원칙은 queue에서 꺼내면서 해당 노드와 자손관계인 노드들을 insert하지만,이 문제에서는 depth가 곧 답이 되기 때문에 temp에 넣어두고 한번에 insert했다. 전체 코드DFS 풀이12345678910111213141516171819202122232425262728293031const oneDiff = (a, b) => { let cnt = 0; for (let i = 0; i < a.length; i++) { if (a[i] !== b[i]) cnt++; ...

문제 링크 분류 / 레벨 / 언어이분탐색 / LV.3 / Javscript 설명문제 독해문제의 조건을 보면입국 대기자는 빈 심사장이 생겨도, 기다린 후에 더 빠른 심사장을 선택할 수 있다.여기서 오해의 소지가 발생하는데,그런 선택이 가능할 뿐이지 대기자가 매순간 자신에게 유리한 선택을 하는 것이 아니다.문제에 따르면 대기자는 심사 누적시간이 가장 적게 걸리게끔 행동해주어야한다.(굳이 말하자면 공항 측에 이득이 되게.. 이런게 문제의 억지임)만약 제대로 독해하지 못했다면, 이분탐색이 아니라 while(n>0){time–} 이런 구현 문제로 풀게 된다. 문제 풀이도출될 수 있는 심사 시간 list 중 가장 최선의 시간을 골라야 한다.이분탐색의 특성상 가능한 답의 리스트를 쭉 뽑아두고또 역으로 대입하고, 범위를 줄이고를 반복하여 풀 것이다. 역으로 대입하기 위한 계산 방정식을 먼저 만들자. 1const cal = x => times.reduc ...

문제 링크 분류 / 레벨 / 언어이분탐색 / LV.3 / Javscript 설명이분탐색 이론left(변수), right(변수)를 딱 필요한 만큼의 범위를 커버할 수 있게 잡아준다.middle(변수) = 소수점버림(left+right/2)로 잡는다.루프를 돌면서 middle이 어떤 조건에 맞는지 판단하고 left또는 right에 넣어준다. ex)1,2,3, … , 98, 99, 100 문제의 요구사항을 분석해 left, right를 잡아준다. (예시로 2, 98)그리고 middle을 바로 계산해 left와 right 중 어디로 넣어줄지 결정한다. 2 —— 98 ( => 50 )2 —— 50 ( => 26 )2 —— 26 ( => 14 )14 —— 26 ( => 20)… 문제풀이이분탐색은 문제없이 짠 것 같은데정확성 케이스와 효율성 테스트에서 계속 한 개씩 통과가 안되었다. 다 ...

문제 링크 분류 / 레벨 / 언어DFS,BFS / LV.3 / Javscript 설명같은 카테고리의 타겟넘버 문제는 처음 DFS 호출이 정적으로 정해져 있었으나,이 문제는 while문안에서 동적으로 DFS를 호출한다.그 이유는 input에 따라서 네트워크 맵의 연결 set이 다르다. 한 set을 다 탐색하고 다음 set을 탐색해야 하는데, 다음 set의 시작노드가 매번 다를 수 밖에 없다. 전체 코드123456789101112131415161718192021function solution(n, computers) { let count = 0; const visited = new Array(n).fill(false); const dfs = (curr, acc) => { computers[curr].forEach((connected, i) => { if (!visited[i] &&am ...

문제 링크 분류 / 레벨 / 언어힙(우선순위큐) / LV.3 / Javscript 설명JS는 C++과 같이 STL로 제공되는 우선순위큐가 없다!대신 코테에서 실행시간을 넉넉히 주므로 걱정할 것도 없다! 이 문제에서는 우선순위큐에 “in” 이벤트가 발생할 때,큐.sort(콜백)으로 원하는 요소를 기준으로 정렬했다. (이런 경우, 콜백을 야무지게 써야한다) 또한 원래 배열에서 “out” 이벤트가 발생할 때,array베타 = array알파.reduce()로 다음 턴에 접근시 시간을 줄였다. 전체 코드123456789101112131415161718192021222324function solution(jobs) { let time = 0; let sum = 0; const divide = jobs.length; const waiting = []; while (jobs.length > 0 || waiting.length &g ...

문제 링크 분류 / 레벨 / 언어힙(우선순위큐) / LV.3 / Javscript 설명힙 힙을 BFS식으로 나열했을 때, 오름차순or내림차순 정렬을 보장하지는 않는다!단, 부모와 자손간의 관계가 확실하기 때문에 루트가 최댓값or최솟값인 것은 보장한다. 힙에 자료를 넣을 때 마지막 index에 넣고(큐 맨 뒤에 넣듯) 부모-자손 간 상향식 비교 힙에서 자료를 빼낼 때 : 최댓값or최솟값인 루트만 빼낼 수 있고 (큐가 맨 앞을 꺼내듯) 루트가 빈자리가 되면 맨 뒷 값을 빼서 가져온다. 그리고 하향식으로 부모-자손간 비교를 한다. 상향식, 하향식 비교가 발생하면 버블 소트와 같이 주체는 자신에게 맞는 자리를 찾아간다. 문제풀이이중우선순위큐라는 자료형이 있었나? 싶었는데 그건 아니었다.그냥 문제 이름이다.최대힙, 최소힙 두 개를 굴려가며 풀려했지만그러기 위해서는 두 힙의 요소들이 매 번 동기화는 것이 상당히 복잡했다.그래서 그냥 구현식으로 ...

문제 링크 분류 / 레벨 / 언어스택,큐 / LV.2 / Javscript 설명스택, 큐를 사용하여 상황을 잘 표현해야 하는 문제이다.while{} 안에서 time++를 하여 타이머를 잰다.그리고 while{} 안에서 1초 동안 발생하는 이벤트를 표현해주면 된다. 전체 코드123456789101112131415161718function solution(bridge_length, weight, truck_weights) { let time = 0; const bridge = new Array(bridge_length).fill(0); //다리 모형 let sumOnBridge = 0; //다리 위 무게 합 do { time++; let out = bridge.shift(); if (out > 0) sumOnBridge -= out; if (sumOnBridge + truck_weights[0] &l ...