본문 바로가기
반응형

Problem Solving/Leetcode25

[Leetcode] 3362. Zero Array Transformation III Difference Array 를 약간의 발상과 함께 사용하는 문제입니다.처음에는 이전 시리즈와 같은 풀이를 적용했으나 오답이 나왔고, 문제를 다시 읽어봤습니다.이전 문제와의 핵심 차이는 주어지는 쿼리를 순서대로 사용하지 않아도 된다는 사실입니다. 이제 친인간 사고적인 Greedy Algorithm 을 사용해 발상을 시작합니다.0번 위치부터 시작하는 쿼리들을 사용 후보 쿼리에 포함합니다.0 위치에 -1 연산을 수행하는 쿼리들부터 사용할 때, 최대한 넓은 범위를 사용하는 순서대로 쿼리를 사용합니다.0으로 만들 수 있다면 다음 위치로 넘어가고, 불가능한 경우 -1을 반환합니다.1번 위치부터 시작하는 쿼리들을 사용 후보 쿼리에 포함합니다.1 위치에 -1 연산을 수행하는 쿼리들부터 사용할 때, 최대한 넓은 범.. 2025. 5. 25.
[Leetcode] 3355. Zero Array Transformation I 보자마자 Segment Tree Lazy Update 문제네! 하고 접근했습니다.2시간을 꼼지락 거리다가 반례를 만나고서야 이게 아니네 싶었습니다.그리고 늦은 시간이라 자야겠다고 눕는 순간 풀이가 떠올랐습다. 우선 Lazy Update 가 안 되는 이유를 보겠습니다.아래와 같은 상태에서 (1, 3) 이라는 쿼리가 들어왔다고 가정하겠습니다.이 문제는 합을 구하는게 아니라 범위에 -1을 수행해 0을 만들 수 있는지를 확인하는 것이 목적입다.따라서, 1번과 2번에는 -1이 들어가지 않고, 3번에만 -1이 수행되어 최상위 노드 값은 0이 아닌 2가 됩니다. 그럼 어떻게 풀어야 할까요?올 해 3월 똑같은 문제를 풀었던 기억이 스쳤습니다. 2025.03.24 - [Problem Solving/Leetcode] - .. 2025. 5. 21.
[Leetcode] 1931. Painting a Grid With Three Different Colors 문제 설명m x n 크기의 격자가 있다.각 칸은 반드시 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 한다.단, 서로 인접한 칸은 같은 색으로 칠할 수 없다.여기서 인접하다는 것은 상하좌우 방향을 의미한다.이 조건을 만족하도록 모든 셀을 칠하는 방법의 수를 구하라.답이 매우 클 수 있으므로 1,000,000,007 (10⁹+7) 로 나눈 나머지를 반환하라. 예시예제 1입력: m = 1, n = 1출력: 3설명: R, G, B 중 하나를 선택할 수 있다 → 3가지예제 2입력: m = 1, n = 2출력: 6설명: 첫 칸을 3가지 중 하나로 칠하고, 다음 칸은 나머지 2가지 중 하나 선택 → 3×2 = 6예제 3입력: m = 5, n = 5출력: 580986설명: 조건을 만족하는 방법 수는 매.. 2025. 5. 20.
[Leetcode] 5. Longest Palindromic Substring 어제 재밌는 DP 문제를 풀고 그 맛에 취해(?) 다른 문제도 도전해봤다. [Leetcode] 2901. Longest Unequal Adjacent Groups Subsequence II역시 Computational Thinking 정수는 Dynamic Programming 문제 유형이다.많이 풀어보고 익숙해지지 않으면 발상하기 쉽지 않은 사고 방식이라 더욱 매력적이다.오랜만에 재밌는 문제였다. 이런 유형 문제를wch18735.tistory.com DP 분류에 들어가니 제일 먼저 눈에 들어온 단어가 Palindrome 이었다.이 유형 문제는 나올 때마다 살짝 쫄아있었는데, 주말이고 시간도 많아 도전했다.결과는 공책 빽빽하게 한 페이지를 다 쓰고서야 풀 수 있었는데, 분발해야지😂 문제 설명문자열 s가.. 2025. 5. 17.
[Leetcode] 2901. Longest Unequal Adjacent Groups Subsequence II 역시 Computational Thinking 정수는 Dynamic Programming 문제 유형이다.많이 풀어보고 익숙해지지 않으면 발상하기 쉽지 않은 사고 방식이라 더욱 매력적이다.오랜만에 재밌는 문제였다. 이런 유형 문제를 많이 풀어보고 싶다는 생각까지 들었다.물론 퇴근하고 여기에 갖다 바친 내 3시간은 전혀 재밌지 않다.사실 설명 자체가 DP 유형 문제 만들기 위해 어거지로 써놓은 느낌도 있고. 문제 설명문자열 배열 words와 정수 배열 groups가 주어진다.두 배열의 길이는 동일하며 각각의 인덱스 i는 하나의 단어와 해당 단어의 그룹을 나타낸다.우리는 [0, 1, ..., n-1]의 인덱스 중 일부를 골라 최장 부분수열(subsequence)을 선택해야 한다.단, 다음 조건을 만족해야 .. 2025. 5. 17.
[Leetcode] 2918. Minimum Equal Sum of Two Arrays After Replacing Zeros 문제 설명양의 정수로 이루어진 두 배열 nums1, nums2가 주어진다.이 두 배열에는 0이 포함될 수 있으며, 각 0은 **양의 정수(1 이상)**로 자유롭게 교체할 수 있다.목표는 다음 두 조건을 동시에 만족하도록 만드는 것이다.nums1과 nums2의 합이 같아야 한다.이 공통된 합은 가능한 한 최소여야 한다.가능하다면 그 최소 합을 반환하고,그럴 수 없다면 -1을 반환한다. 예시예제 1입력: nums1 = [3,2,0,1,0], nums2 = [6,5,0]출력: 12설명:nums1의 0을 2와 4로 대체 → [3,2,2,1,4], 합 = 12nums2의 0을 1로 대체 → [6,5,1], 합 = 12가능한 최소의 공통 합이다.예제 2입력: nums1 = [2,0,2,0], nums2 = [1,4.. 2025. 5. 11.
반응형

티스토리툴바