본문 바로가기

🏃 algorithm/leetcode93

LeetCode 2390 - Removing Stars From a String (Medium) 💡 문제 LeetCode - 2390번 🎯 풀이 과정 별표 (*)를 포함한 문자열 s 에서 다음 규칙에 따라 모든 별표가 제거된 문자열을 반환하는 문제입니다. 별표가 있을 경우 해당 별표보다 앞쪽에 위치한 가장 가까운 문자를 제거합니다. 스택을 활용하면 간단하게 해결이 가능한데, 입력으로 주어지는 문자열의 길이가 크기 때문에 (10^5) 문자열을 순회하며 자료구조에 하나씩 push, pop 하기 보다는 다른 방법을 사용했습니다. 규칙을 활용해서 문자열의 가장 뒤쪽 부터 순회를 해줍니다. 이때 * 를 만나면 answer 에 추가하지 않고 별표의 개수를 계속 세어주다가 일반 알파벳을 발견하면 저장해놨던 별표 개수를 하나씩 줄이고, 만약 저장되어있는 별표 개수가 없다면 그 문자를 answer 에 추가해줍니다... 2023. 4. 24.

LeetCode 1603 - Design Parking System (Easy) 💡 문제 LeetCode - 1603번 🎯 풀이 과정 3종의 차량 (big, medium, small) 을 수용하는 주차장 시스템을 구현하는 문제입니다. carType 인덱싱을 편하기 하기 위해 배열의 크기를 하나 늘려서 사용합니다. 👨‍💻 코드 /** * @param {number} big * @param {number} medium * @param {number} small */ var ParkingSystem = function(big, medium, small) { this.parkingSlots = [0, big, medium, small] }; /** * @param {number} carType * @return {boolean} */ ParkingSystem.prototype.addCar .. 2023. 4. 24.

LeetCode 15 - 3Sum (Medium) 💡 문제 LeetCode - 15번 🎯 풀이 과정 주어진 배열에서 3개의 원소의 조합 중 합이 0인 것들을 중복없이 모두 찾는 문제입니다. 다만 입력 크기를 고려해서 일반 조합 알고리즘보다 효율적인 방법이 필요합니다. 투 포인터 알고리즘을 활용하면, 특정 합 S 를 만족하는 배열 쌍을 중복없이 찾는데 활용할 수 있습니다. 이때 배열은 정렬이 된 상태여야합니다. (중복 제거를 위해) 이 문제를 약간 변형해보면 세 원소 중 가장 첫번째 요소를 pivot 으로 정하고, 나머지 두 요소는 pivot 을 제외한 구간에서 sum - arr[pivot] 을 찾는 문제로 해석할 수 있습니다. 이때 중복 제거를 위해 pivot 이 바로 직전 pivot 값과 동일할 경우 무시하고, 마찬가지로 나머지 두 요소 중 첫번째 요.. 2023. 4. 24.

LeetCode 13 - Roman to Integer (Easy) 💡 문제 LeetCode - 13번 🎯 풀이 과정 로마 숫자를 변환하는 문제입니다. 로마 숫자는 감산, 가산 연산법을 함께 I, V, X, L, C, D, M 의 문자를 나열하여 표현합니다. 그렇기에 앞 자리부터 순회하면서 그 다음 숫자와 크기를 비교하여 합산해야할 크기를 알아냅니다. 이때 반복문 대신 재귀 호출을 사용하면 좀 더 간결하게 구현할 수 있습니다. 👨‍💻 코드 /** * @param {string} s * @return {number} */ var romanToInt = function(s) { const roman = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000, } function transform(here) { i.. 2023. 4. 24.

LeetCode 994 - Rotting Oranges (Medium) 💡 문제 LeetCode - 994번 🎯 풀이 과정 매 단위시간(minute) 마다 썩은 오렌지에 인접한 4방향에 위치한 오렌지가 함께 썩는다고 할때 주어진 grid 에서 모든 오렌지가 썩기까지 걸리는 시간을 구하는 문제입니다. 일반적인 BFS 탐색에서 약간의 변형이 필요한 유형입니다. 썩은 오렌지를 queue 에 넣어주고 queue 가 비어질때까지 반복해야지 각각의 단위 시간마다 현재 queue 에 담겨있는 오렌지들에 대해 BFS 를 할 수 있습니다. 보통 BFS 를 할 때 중복 방문을 피하기 위해 visit 같은 자료구조를 만들어 이용하는데, 여기서는 오렌지가 썩은 상태일 때를 이미 방문한 위치로 판단이 가능하므로 방문여부를 위한 별도의 자료구조는 만들어주지 않고 상태값으로 판단하도록 할 수 있습니다.. 2023. 4. 24.

LeetCode 24 - Swap Nodes in Pairs (Medium) 💡 문제 LeetCode -24번 🎯 풀이 과정 뒤에서부터 노드의 순서를 재귀적으로 변경(swap)하는 요구조건을 구현하는 문제입니다. 포인터를 바꿔주기 위해 재귀호출 시 현재 노드와 이전노드에 대한 참조를 함께 전달하도록 했습니다. 👨‍💻 코드 /** * 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 swapPairs = function(head) { funct.. 2023. 2. 20.

이전 1 2 3 4 5 ··· 16 다음

티스토리툴바