본문 바로가기

Web Development/algorithm

 (27)
[Algorithm][LeetCode 3477][Easy] Fruits Into Baskets II 문제 설명두 개의 배열 fruits, baskets가 주어집니다.fruits[i]: i번째 과일의 수량baskets[j]: j번째 바구니의 용량다음 조건에 따라 과일을 왼쪽에서 오른쪽 방향으로 바구니에 담습니다.각 과일은 자신보다 크거나 같은 용량을 가진 바구니 중 가장 왼쪽에 있는 바구니에 들어갈 수 있습니다.각 바구니에는 한 종류의 과일만 담을 수 있습니다.들어갈 수 있는 바구니가 없다면, 해당 과일은 남겨집니다.반환값: 바구니에 들어가지 못한 과일의 개수 예시// 예시 1입력: fruits = [4, 2, 5], baskets = [3, 5, 4]설명:- fruits[0] = 4 → baskets[1] = 5에 배치- fruits[1] = 2 → baskets[0] = 3에 배치- fruits[2..
[Algorithm][LeetCode 3442][Easy] Maximum Difference Between Even and Odd Frequency I 문자열에서 홀수/짝수 빈도 차이 최대값 구하기 - JavaScript이번 글에서는 문자열 내 각 문자의 빈도를 분석하여, 홀수 빈도를 가진 문자와 짝수 빈도를 가진 문자 사이의 빈도 차이 중 가장 큰 값을 구하는 문제를 다룹니다.문제 설명주어진 문자열 s에서 다음 조건을 만족하는 차이 diff = a1 - a2의 최대값을 구합니다.a1: 홀수 빈도를 가진 문자a2: 짝수 빈도를 가진 문자제약 조건:3 ≤ s.length ≤ 100s는 소문자 알파벳으로만 구성홀수 및 짝수 빈도를 갖는 문자가 각각 최소 1개 이상 존재함예시// 예시 1입력: s = "aaaaabbc"'a' → 5 (홀수), 'b' → 2 (짝수)결과: 5 - 2 = 3// 예시 2입력: s = "abcabcab"'a' → 3 (홀수), '..
[Algorithm][LeetCode 2434][Medium] Using a Robot to Print the Lexicographically Smallest String 문제 설명문자열 s가 주어지고, 로봇은 비어 있는 문자열 t를 들고 있습니다.다음 두 가지 작업 중 하나를 반복할 수 있습니다:s의 첫 번째 문자를 제거해서 t의 끝에 붙입니다.t의 마지막 문자를 제거해서 종이에 적습니다.이 과정을 s와 t가 모두 비어질 때까지 반복하고, 종이에 적힌 최종 문자열이 사전순으로 가장 작아야 합니다.접근 방식스택: t는 후입선출 구조이므로 스택으로 모델링그리디: 매 순간 t의 마지막 문자가 앞으로 나올 문자보다 작거나 같으면 즉시 pop1. 현재 위치 이후에 가장 작은 문자 구하기현재 위치 이후에 가장 작은 문자를 알 수 있어야 그리디하게 판단할 수 있습니다.이를 위해 문자열 s를 뒤에서부터 스캔하여 minSuffix 배열을 만들어줍니다.// s[i:]에서 가장 작은 문자를..
[Algorithm][LeetCode 2929][Medium] Distribute Candies Among Children II 문제두 양의 정수 n과 limit이 주어졌을 때,세 명의 아이에게 사탕을 나누어 주는 방법의 총 수를 반환하시오. 단, 어떤 아이도 limit개를 초과해서 받을 수 없다.예시 1:Input: n = 5, limit = 2Output: 3설명: (1, 2, 2), (2, 1, 2), (2, 2, 1) 의 3가지 방법 존재예시 2:Input: n = 3, limit = 3Output: 10설명: (0,0,3), (0,1,2), (0,2,1), (0,3,0), (1,0,2), (1,1,1), (1,2,0), (2,0,1), (2,1,0), (3,0,0)제약 사항1 ≤ n ≤ 1061 ≤ limit ≤ 106풀이1. 브루트포스 접근법a, b의 값을 고정하면 c는 n - a - b로 자동 결정됩니다.하지만 lim..
[Algorithm][LeetCode 3355][Medium] Zero Array Transformation I 이번 문제는 차분 배열(Difference Array) 개념을 활용하여, 수많은 구간 쿼리를 빠르게 처리할 수 있는지 평가하는 문제다. 초기 풀이 방식에서 성능 개선을 거쳐 AI가 최종 추천하는 1-pass 최적화 방식까지 3단계로 접근 방법을 소개한다.문제 설명정수 배열 nums와 2차원 배열 queries가 주어진다. 각 쿼리는 [li, ri] 형태로, 해당 구간에서 원하는 일부 인덱스를 선택하여 값을 1만큼 감소시킬 수 있다. 모든 쿼리를 순서대로 처리한 후, 모든 원소가 0인 배열로 만들 수 있는지 여부를 판단해야 한다.접근 1단계: 초기 코드 (직접 반복)각 쿼리 범위를 직접 순회하며, 각 인덱스가 몇 번 감소할 수 있는지를 map에 기록하는 방식이다.var isZeroArray = functi..
[Algorithm][LeetCode 2094][Easy] Finding 3-Digit Even Numbers You are given an integer array digits, where each element is a digit. The array may contain duplicates.You need to find all the unique integers that follow the given requirements:The integer consists of the concatenation of three elements from digits in any arbitrary order.The integer does not have leading zeros.The integer is even.Return a sorted array of the unique integers.Example 1:Input: di..
[Algorithm][LeetCode 75][Medium] Sort Colors 문제Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.You must solve this problem without using the library's sort function.Example 1Input: nums = [2,0,2,1,1,0]Output: [0,0,1..
[Algorithm][LeetCode 1550] Three Consecutive Odds 연속된 홀수 판별하기 (Three Consecutive Odds)문제: 주어진 정수 배열 arr에 대해, 연속된 홀수 숫자 3개가 존재하면 true를 반환하고, 그렇지 않으면 false를 반환하라.1. 접근 방식연속된 홀수의 개수를 카운트할 변수 count를 생성한다.배열을 순회하면서 현재 숫자가 홀수면 count를 1 증가시킨다.짝수가 나오면 count를 0으로 초기화한다.count가 3이 되는 순간 true를 반환한다.끝까지 반복했지만 3이 되지 않으면 false를 반환한다.2. 자바스크립트 코드/** * @param {number[]} arr * @return {boolean} */var threeConsecutiveOdds = function(arr) { let count = 0; fo..

티스토리툴바