코딩곳간

문제 링크 문제 풀이user_id가 banned_id에서 여러 개에 걸릴 수 있다. 그래서 NxN의 완전탐색으로 풀면 경우의 수를 놓칠 수 있다. 재귀(DFS)로 user_id와 banned_id가 매칭된 상태를 다음 재귀로 넘겨주며가능한 상황을 다 count해야 한다. 전체 코드123456789101112131415161718192021222324const checkWord = (a, b) => new RegExp("^" + b.split("*").join(".") + "$").test(a);function solution(user_id, banned_id) { let temp = {}; const compare = (users, ban, depth) => { if (depth < banned_id.length) users.forEach(( ...

문제 링크 문제 풀이구현 문제이다.결국 dartResult의 모든 요소를 다 점검해야하므로 시간복잡도는 n이 된다. 가능한 가독성 좋게 풀려고 했다. 10 체크 0-9 체크 이외 문자 체크 => cal() 호출 전체 코드12345678910111213141516171819202122232425262728293031323334353637383940function solution(dartResult) { const darts = dartResult.split(""); let scores = [0, 0, 0]; let i = -1; const cal = (input) => { switch (input) { case "D": scores[i] = Math.pow(scores[i], 2); break; case "T": ...

문제 링크 문제 풀이mappingfiles 원본의 정렬본을 반환해야 하므로files의 각 file을 직접 HEAD, NUMBER, TAIL로 분리하지 않고각 file과 필요한 요소로 추가하여 만든 객체를 새로 mapping했다. stable sort[1,1,2,3]을 내림차순으로 정렬하면 [3,2,1,1]이다.<1,1>은 “내림차순”이라는 조건에 해당되지 않아[3,2,1,1] 마지막에 <1,1>이 그대로 있다.그리고 이 <1,1>이 원래의 <1,1>과 같은 순서인지 구별할 수 없다. 하지만 [[1,”ㄱ”], [1,”ㄴ”], [2,”ㄷ”], [3,”ㄹ”]]를value[0]을 기준으로 내림차순 정렬한다면 (sort((a,b)=>(b[0]-a[0])))정렬 후 마지막 1이 어디에 있던 1인지 알 수 있다. 이처럼 나머지 요소를 확인 가능한 정렬을 할 때,서로 정렬될 필요가 없는 요소들은 처음 순서대로 있도록 만드는 것이stable sort다 ...

문제 링크 문제 풀이구현의 성격이 강하다.단 문제의 조건을 놓치지 않고 필요한 함수를 정의해야한다. 문제의 C#, D# 같이 #이 붙는 경우 문자열은 2개이지만 1개로 계산해야하므로소문자 c, 소문자 d등으로 대체했다. 전체 코드12345678910111213141516171819202122232425262728293031323334const converter = (input) => input .split("") .reduce( (acc, cur) => cur === "#" ? acc.concat(acc.pop().toLowerCase()) : acc.concat(cur), [] ) .join("");const timer = (start, end) => parseInt(end.slice(0, 2)) * 60 - parseInt(start.slice(0, 2) ...

문제 링크 문제 풀이재귀, 조건 검증재귀안에 재귀를 걸어주는데,중간에 조건을 검증하여 필터링해야한다. node 요소가 없으면 return idx가 node 요소의 길이보다도 긴 경우 필터링 idx의 위치에서 서로 다른 node 필터링 + recur() 남은 node가 하나라면 return, 아니라면 recur() 로그 확인문제에서 요구하는 답은각 search 입력 수의 합이다.그런데 각 search 수가 실제랑 다르면서우연스레 누적 값이 같은 경우도 생길 수 있다. 그래서 첫 줄의 cnt를 0 대신 []로 두고“cnt+=값”대신 “cnt.push(값)”으로 충분히 확인해본 후마지막에 “cnt+=값”으로 바꿔서 제출하는 것이 확실하다. 전체 코드1234567891011121314151617181920212223242526function solution(words) { let cnt = 0; const recur = (node, idx) => &# ...

문제 링크 문제 풀이두 개의 배열을 사용해야 한다. dic, answerfor문을 돌면서 조건을 검증하고 두 개의 배열 중 한 곳에 넣어준다.최종적으로 answer를 return한다. 이 문제도 그렇지만,어떤 한 턴만의 요소를 필요로 하지 않고앞 뒤 요소를 끌어와 함께 사용해야 하는 경우가 있다.이럴 때 reduce를 사용하면 조금 더 깔끔해진다. 전체 코드1234567891011121314151617function solution(msg) { const dic = "~ABCDEFGHIJKLMNOPQRSTUVWXYZ".split(""); const answer = []; answer.push( dic.indexOf( msg.split("").reduce((acc, cur) => { if (dic.indexOf(acc + cur) > -1) return acc + cur; ...

문제 링크 문제 풀이구현의 성격이 강한 문제이다.진수 변환하는 방법을 알고 있어야 빠르고 정확하게 풀 수 있다.진수 계산 전체 코드123456789101112131415function solution(n, t, m, p) { let num = 0; let fullString = ""; while (fullString.length < t * m) { fullString += num.toString(n).toUpperCase(); num++; } return fullString .split("") .filter((v, i) => (i + 1 - p) % m === 0) .slice(0, t) .join("");}

문제 링크 분류 / 레벨 / 언어그래프 / LV.3 / Javscript 설명인접 행렬인접 행렬 adjacent matrix를 사용한다. 인접 행렬 (행,열)을 (a,b)라고 할 때 a가 b를 이기면 1, a가 b에게 지면 -1을 저장한다.비기는 경우는 없으므로 생각하지 않는다.a와 b의 승패를 도저히 알 수 없을 경우 0(default)을 저장한다. 그리고 배열의 index에 편하게 접근하기 위해 (n+1)x(n+1) 규모의 인접 행렬을 사용한다. 풀이 과정 input만으로도 알 수 있는 승패 결과는 인접 행렬에 저장한다. 3중첩 반복문으로 (a,b) 위치에서 다른 행에 접근해 승패 정보를 전파한다.(like 플로이드와샬) 3중첩이나 했기 때문에 전파 과정에 빈틈이 생길 수 없다.(input을 하나씩 추출하면서 정보를 전파했을 때는 빈틈이 생겼다.) 최종 카운트할 때는 index = 0, index_x === ...

문제 링크 분류 / 레벨 / 언어그래프 / LV.3 / Javscript 설명그래프 용어정점 vertex간선 edge방향성 directed, undirected사이클 cyclic, acyclic가중치 weighted완전(정점,간선 full) complete 그래프를 표현하는 자료구조인접행렬과 인접리스트 방식이 있다.모든 노드를 탐색할 경우는 두 방식 모두 시간복잡도가 똑같다. 인접행렬방향성 있을 때 시간복잡도 : O(V^2)방향성 없을 때 시간복잡도 : O(V^2 / 2) 간선밀도가 높은 밀집그래프에 유리 let a: boolean[][] = [[true, false],[false, true]]let b: int[][] = [[1, 2],[-1, 5]] i에서 j로 방향성 표현 가능 가중치(int) 표현 가능 단 가중치 표현할 때 연결되지 않은 정점간 간선은 -1일지 0일지 상황마다 다름(JS는 그냥 숫자 사이에 nul ...

문제 링크 분류 / 레벨 / 언어동적계획법(Dynamic Programming) / LV.4 / Javscript 설명DP문제의 특징travel의 수가 3~100이다.매 노드에서 travel을 2개 택할 수 있으므로완전탐색, 재귀로 푼다면 최악의 경우 2의 100제곱 만큼 연산이 필요하다. 126,7650,6002,2822,9401,4967,0320,5376양, 자, 해, 경, 조, 억, 만, 천 이 수는 너무 크기 때문에차라리 1,000,000이나 5,000,000정도의 크기를메모리에 할당해버리고 n번 연산하는 것이 훨씬 빠르다. memoization travel의 길이 + 1 = 노드의 개수 = node K + 1 = 각 노드에서 각 시간 별로 가능한 최대 돈 = time => array[node][time] = maximun money 시간복잡도최악의 경우 100 x 100,000 ...