[LeetCode] 133. Clone Graph, Medium
·
CodingTest/LeetCode
1. 문제val와 neighbors 필드를 가지는 노드로 구성된 그래프가 주어질 때, 이를 원래 노드를 참조하지 않는 새로운 노드로 구성된 그래프를 구성하라.2. 해결/** * Definition for _Node. * class _Node { * val: number * neighbors: _Node[] * * constructor(val?: number, neighbors?: _Node[]) { * this.val = (val===undefined ? 0 : val) * this.neighbors = (neighbors===undefined ? [] : neighbors) * } * } * */function DFS(node: _Node, ..
[LeetCode] 150. Evaluate Reverse Polish Notation, Medium
·
CodingTest/LeetCode
1. 문제역 폴란드 표기법으로 제공되는 문자열 배열의 계산 결과를 반환하라.2. 해결function evalRPN(tokens: string[]): number { const stack = []; const operator = ['*', '-','+','/']; for(const token of tokens) { if(!operator.includes(token)) stack.push(Number(token)); else { const target1 = stack.pop(); const target2 = stack.pop(); if(token === '+') stack.push(tar..
[LeetCode] 739. Daily Temperatures, Medium
·
CodingTest/LeetCode
1. 문제매 일 측정한 온도 배열 temperatures가 주어질 때, 각 요소 별로 다음으로 온도가 높아지기 까지 며칠이 걸리는 지 계산한 배열을 반환하라.2. 해결function dailyTemperatures(temperatures: number[]): number[] { const result = new Array(temperatures.length).fill(0); const stack = []; for(let i =0; i 0 && temperatures[i] > temperatures[stack[stack.length-1]]) { const prevIndex = stack.pop(); result[prevIndex] = i - prevI..
[LeetCode] 20. Valid Parentheses, Easy
·
CodingTest/LeetCode
1. 문제(){}[] 각 문자로 구성된 문자열이 주어질 때, 옳바른 괄호로 구성되어 있는지 반환하라.2. 해결function isValid(s: string): boolean { const stack = new Array(); const map = { ')' : '(', ']' : '[', '}' : '{' } for(const char of s) { if(!map.hasOwnProperty(char)) stack.push(char); else { const top = stack.pop(); if(top !== map[char]) return false; } ..
[LeetCode] 155. Min Stack, Medium
·
CodingTest/LeetCode
1. 문제요구사항에 맞게 min stack을 구현하라.모든 함수의 시간 복잡도는 O(1)이 되어야 한다.2. 해결class MinStack { stack: number[]; minstack: number[]; constructor() { this.stack = new Array(); this.minstack = new Array(); } push(val: number): void { this.stack.push(val); if(this.minstack.length === 0 || val 최소값 관리에 막혔는데, 별도로 배열을 한 개 더 둬서 관리하면 된다.
[LeetCode] 279. Perfect Squares, Medium
·
CodingTest/LeetCode
1. 문제정수 n이 주어질 때, 완전 제곱수의 합으로 만들 수 있는 최소 개수를 반환하라.2. 해결function numSquares(n: number): number { const queue:[number, number][] = [[n, 0]]; const visit = new Set(); while(queue.length > 0) { const [curr, step] = queue.shift(); const sqrt = Math.floor(Math.sqrt(curr)); for(let i = sqrt; i > 0; i--){ const next = curr - i * i; ..
[LeetCode] 752. Open the Lock, Medium
·
CodingTest/LeetCode
1. 문제4자리 문자열로 구성된 deadends 배열과 target 문자열이 주어질 때, 몇 번의 과정을 거쳐서 target 문자열에 도달할 수 있는지 반환하라. 불가능하면 -1을 반환2. 해결function openLock(deadends: string[], target: string): number { const deadSet = new Set(deadends); if(deadSet.has("0000")) return -1; const queue: [string, number][] = [["0000",0]] const visit = new Set(); visit.add("0000"); while(queue.length > 0) { const [curr, t..
[LeetCode] 200. Number of Islands, Medium
·
CodingTest/LeetCode
1. 문제m x n 크기의 2차원 배열이 주어지고, 각 요소는 1(섬), 0(바다)로 구성되어 있을 때, 존재하는 섬의 개수를 반환하라.섬은 수직 또는 수평으로 다른 인접한 섬을 가지고 있고, 바다로 둘러쌓여 있다. (모서리는 바다로 가정)2. 해결const row = [-1, 1, 0, 0];const col = [0, 0, -1, 1];function DFS(grid, x, y) { if (x = grid.length || y = grid[0].length || grid[x][y] === '0') return; grid[x][y] = '0' for(let k=0; k 0) { const [x,y] =queue.shift(); ..
[LeetCode] 622. Design Circular Queue, Medium
·
CodingTest/LeetCode
1. 문제요구사항에 맞는 Circular Queue를 구현하라2. 해결class MyCircularQueue { queue: Array; front: number; rear: number; constructor(k: number) { this.queue = new Array(k+1).fill(null); this.front = 0; this.rear = 0; } enQueue(value: number): boolean { if(this.isFull()) return false; this.queue[this.rear] = value; this.rear = (this..
[LeetCode] 61. Rotate List, Medium
·
CodingTest/LeetCode
1. 문제단일 연결리스트와 정수 k가 주어질 때, k만큼 오른쪽으로 회전한 리스트를 반환하라.2. 해결/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */function rotateRight(head: ListNode | null, k: number): Lis..