TIL
2023. 6. 13.
TIL #055
오늘 한 것
알고리즘
프로그래머스 고득점 키트
- 정렬
- K번째 수
const calc = (arr, command) => { const [start, end, num] = command; const answer = arr.slice(start - 1, end).sort((a, b) => a - b)[num - 1]; return answer; } const solution = (array, commands) => commands.map(command => calc(array, command));- 가장 큰 수
const isZeroArr = (arr) => { return JSON.stringify([...new Set(arr)]) === '[0]'; } const compareNum = (a, b) => { const num1 = (a.toString() + b.toString()) * 1; const num2 = (b.toString() + a.toString()) * 1; return num1 > num2 ? -1 : 1; } const solution = (numbers) => { if(isZeroArr(numbers)) return '0'; return numbers.sort((a, b) => compareNum(a, b)).join(''); };- H-Index
const solution = (citations) => { if(JSON.stringify([...new Set(citations)]) === '[0]') return 0; citations.sort((a, b) => a - b); for(let i = 0; i < citations.length; i++) { const num = citations[i]; const idx = citations.length - i; if(num >= idx) return citations.length - i; } }
- 완전탐색
- 최소직사각형
const sizeMap = (size) => { const [a, b] = size; return a > b ? [b, a] : [a, b]; } const solution = (sizes) => { const [width, height] = sizes .map(size => sizeMap(size)) .reduce((acc, cur) => { const a = acc[0] > cur[0] ? acc[0] : cur[0]; const b = acc[1] > cur[1] ? acc[1] : cur[1]; return [a, b]; }, [0, 0]); return width * height; }- 모의고사
const rules = [ [1, 2, 3, 4, 5], [2, 1, 2, 3, 2, 4, 2, 5], [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] ]; const countAnswer = (answers, ruleNum) => { const rule = rules[ruleNum]; const answer = answers .filter((answer, i) => rule[i % rule.length] === answer) .length; return answer; } const solution = (answers) => { const counts = [ countAnswer(answers, 0), countAnswer(answers, 1), countAnswer(answers, 2) ]; const max = Math.max(counts[0], counts[1], counts[2]); return [1, 2, 3].filter(v => counts[v - 1] === max); }- 전력망을 둘로 나누기
const solution = (n, wires) => { let answer = n; for (let i = 0; i < wires.length; i++) { const tree = makeTree(n, wires, i); const startNode = tree.findIndex((v) => !!v.length); const nodeCount = countNode(tree, startNode); const abs = Math.abs(nodeCount * 2 - n); if (abs < answer) answer = abs; } return answer; }; const makeTree = (n, wires, exceptIdx) => { const tree = Array.from({ length: n + 1 }, () => []); wires.forEach((wire, idx) => { if (idx === exceptIdx) return; const [a, b] = wire; tree[a].push(b); tree[b].push(a); }); return tree; }; const countNode = (tree, startNode) => { const visited = []; let needVisit = [startNode]; while (!!needVisit.length) { const node = needVisit.shift(); if (!visited.includes(node)) { visited.push(node); needVisit = [...tree[node], ...needVisit]; } } return visited.length; };- 모음사전
let idx = 0; const result = {}; const vowels = [..."AEIOU"]; function solution(word) { dfs("", 0); return result[word]; } const dfs = (word, length) => { if (length > 5) return; result[word] = idx++; vowels.forEach((vowel) => { dfs(word + vowel, length + 1); }); };
알고리즘 문제 분석 및 풀이
오늘 느낀 점
DFS와 BFS를 정복했다. 확실히 1년 전에 비해 컴퓨팅 사고가 많이 발전한 것이 느껴져서 기쁘다.
오늘 새로 만들고 싶은 서비스를 생각해냈다. 쓰담쓰담쓰담 : 하루 3번 나를 사랑하기. 사실 지금은 취준에 집중해야 되는게 맞는데, 내가 사용하기 위해서 직접 구현하고 싶다. 참고로 프로젝트 이름 후보로는 ‘나를 아껴주세요!’, ‘나르시스’ 등이 있었다.