본문 바로가기

👨‍💻📱✍️🎢314

LeetCode 19 - Remove Nth Node From End of List (Medium) 문제 LeetCode - 19번 풀이 과정 링크드 리스트에서 뒤에서 n 번째 노드를 삭제하는 연산을 구현하는 문제입니다. 뒤에서 n 번째 노드를 찾기 위해서 우선 리스트의 전체 크기를 알아낸 다음, 이동해야 하는 offset 을 계산합니다. 이후 두 개의 포인터를 활용해서 next 속성을 재지정하면 됩니다. 코드 /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @r.. 2021. 3. 3.
LeetCode 79 - Word Search (Medium) 문제 LeetCode - 79번 풀이 과정 이차원 배열에서 인접한 문자들을 이용해서 특정 단어를 만들 수 있는지 판단하는 문제입니다. 백트래킹 을 활용해서 문자가 일치하지 않으면 다음 위치를 찾도록 탐색을 하면 됩니다. 또한 원하는 단어를 찾으면 다른 문자들은 탐색하지 않고 바로 true 를 반환하도록 하였습니다. 코드 /** * @param {character[][]} board * @param {string} word * @return {boolean} */ var exist = function (board, word) { const dx = [0, 0, 1, -1]; const dy = [1, -1, 0, 0]; function dfs(x, y, depth, visit) { if (board[x][.. 2021. 3. 3.
LeetCode 771 - Jewels and Stones (Easy) 문제 LeetCode - 771번 풀이 과정 특정 문자열에 포함된 문자의 개수를 찾는 문제입니다. 문자 탐색의 기준이 되는 문자열 J 를 해싱해서 저장한 다은 S 를 하나씩 순회하며 해당 문자가 J 에 존재하는지 찾습니다. 이렇게 하면 O(N) 에 탐색을 수행할 수 있습니다. 코드 /** * @param {string} J * @param {string} S * @return {number} */ var numJewelsInStones = function (J, S) { const hashTable = {}; [...J].forEach((c) => (hashTable[c] = 1)); const answer = [...S].filter((c) => hashTable[c]); return answer.le.. 2021. 3. 3.
LeetCode 5 - Longest Palindromic Substring (Medium) 문제 LeetCode - 5번 풀이 과정 가장 긴 팰린드롬을 구하는 문제입니다. 만약 dp(i, j) = i에서 j까지의 가장 긴 팰린드롬의 길이 라고 정의한다면 다음과 같은 점화식을 세울 수 있습니다. dp(i, j) = if dp[i] == dp[j] & dp(i+1, j-1) is palindrome, dp(i+1, j-1) + 2 else 0 기저 사례로 각 문자는 길이가 1인 팰린드롬이라는 것에 유의하여 구현하였습니다. 코드 /** * @param {string} s * @return {string} */ var longestPalindrome = function (s) { let answer = ""; const dp = new Array(s.length) .fill(null) .map((x).. 2021. 3. 3.
LeetCode 206 - Reverse Linked List (Easy) 문제 LeetCode - 206번 풀이 과정 연결 리스트 의 포인터를 뒤집는 연산을 구현하는 문제입니다. 가장 직관적인 방법으로 재귀 호출 을 이용해서 구현하였습니다. 각각의 재귀 호출은 다음 노드부터 끝 노드까지의 뒤집힌 결과를 기대하며 해당 결과를 토대로 현재 노드의 포인터 값을 변경합니다. 코드 /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var rev.. 2021. 3. 3.
LeetCode 136 - Single Number (Easy) 문제 LeetCode - 104번 풀이 과정 하나의 숫자만 1개가 존재하고 나머지 숫자들은 2개씩 존재하는 배열에서 1개 존재하는 숫자를 single number 라고 했을 때 해당 수를 찾는 문제입니다. 문제 조건에서 O(N) 에 추가 메모리 공간을 사용하지 않고 구현하는 방법을 찾아야합니다. 이를 위해서 비트 연산자 중에서 xor 를 활용하도록 합니다. xor 연산은 서로 다른 비트에서만 1이고 나머지는 0이기 때문에 같은 숫자끼리 xor 을 하면 0이 됩니다. 따라서 single number 를 제외한 모든 수는 2개씩 존재하기 때문에 xor 결과 0이 되고 0 ^ single number = single number 로 구할 수 있습니다. 코드 /** * @param {number[]} nums .. 2021. 3. 3.

티스토리툴바