LeetCode 1431. Kids With the Greatest Number of Candies

🚀 문제: 1071. Greatest Common Divisor of Strings 플랫폼: LeetCode 번호: 1071 제목: Greatest Common Divisor of Strings 링크: https://leetcode.com/problems/greatest-common-divisor-of-strings/ 난이도: Easy   📝 문제 설명 두 문자열 str1과 str2가 주어졌을 때, 두 문자열의 문자열 최대공약수(GCD of Strings)를 찾는 문제입니다. 문자열 t가 문자열 s를 나눈다는 것은 s = t + t + ... + t (즉, t가 하나 이상 반복되어 s와 같아짐)와 같이 정의됩니다. 우리는 str1과 str2를 모두 나누는 가장 긴 문자열 x를 찾아야 합니다. 예시 1: 입력: str1 = "ABCABC", str2 = "ABC" 출력: "ABC" 설명: "ABC"는 "ABCABC" ("ABC" + "ABC")를 나누고, "ABC"는 "ABC" ("ABC")를 나눕니다. 예시 2: 입력: str1 = "ABABAB", str2 = "ABAB" 출력: "AB" 설명: "AB"는 "ABABAB" ("AB" + "AB" + "AB")를 나누고, "AB"는 "ABAB" ("AB" + "AB")를 나눕니다. 예시 3: 입력: str1 = "LEET", str2 = "CODE" 출력: "" 설명: 두 문자열을 모두 나누는 공통 문자열이 없습니다. 🤔 풀이 아이디어: 길이의 최대공약수를 기반으로 한 탐색 이 문제는 두 문자열을 공통으로 나누는 가장 긴 부분 문자열을 찾는 것입니다. 제가 생각한 접근 방식은 다음과 같습니다. 길이의 최대공약수(GCD) 활용: 만약 두 문자열 str1과 str2에 공통적으로 반복되는 부분 문자열 X가 존재한다면, str1의 길이는 len(X)의 배수여야 하고, str2의 길이도 len(X)의 배수여야 합니다. 따라서, 가능한 X의 길이 len(X)는 len(str1)과 len(str2)의 공약수여야 합니다. 우리가 찾는 가장 긴 X의 길이는 gcd(len(str1), len(str2))의 약수 중 하나가 될 것입니다. 후보 길이 탐색: 가장 긴 X를 찾아야 하므로, 가능한 길이 중 가장 긴 것부터 확인합니다. gcd(len(str1), len(str2))부터 시작해서 1까지 길이를 줄여가며 각 길이 i에 대해 다음을 확인합니다. 길이 i를 가지는 str1의 접두사(prefix) 또는 str2의 접두사를 후보 문자열 P로 설정합니다. (예: str1[:i] 또는 str2[:i]) str1이 이 후보 문자열 P를 반복하여 구성되는지 확인합니다. (즉, str1 == P * (len(str1) // i)) str2도 이 후보 문자열 P를 반복하여 구성되는지 확인합니다. (즉, str2 == P * (len(str2) // i)) 두 조건이 모두 만족되면, 해당 P가 현재까지 찾은 가장 긴 공통 divisor이므로 반환합니다. 특별 케이스 처리: 만약 str1과 str2의 길이가 같다면, 두 문자열이 완전히 동일해야 그 문자열 자체가 GCD가 되고, 다르면 공통 divisor는 없습니다. 이 아이디어를 바탕으로 코드를 작성했습니다. 💻 코드 (Python) 제가 직접 작성한 코드와 주석입니다. Python from typing import List # List는 이 문제에서 직접 사용되지 않지만, 일반적인 LeetCode 환경을 위해 포함될 수 있습니다. # GCD 존재하려면 str1,str2 둘다 반복문자이거나 아니면 str1자체가 str2의 반복문자여야함. # 반복문자인지 확인하려면 두문자열의 길이의 최대공약수를 구하고 # 최대공약수의 약수의 길이만큼의 문자열의 배수가 원래 문자열이 되야함. class Solution: def gcd(self, a: int, b: int) -> int: """두 정수의 최대공약수를 유클리드 호제법으로 계산합니다.""" while b: #b가 0이 될때까지 반복 a, b ...

🚀 문제: 872. Leaf-Similar Trees 플랫폼: LeetCode 번호: 872 제목: Leaf-Similar Trees 링크: https://leetcode.com/problems/leaf-similar-trees/ 난이도: Easy 📝 문제 설명 두 개의 이진 트리 root1과 root2가 주어졌을 때, 이 두 트리가 잎이 비슷한(Leaf-Similar)지 확인하는 문제입니다. 두 트리가 잎이 비슷하다는 것은, 각 트리의 리프 노드(Leaf Node) 값들을 왼쪽에서 오른쪽 순서대로 나열했을 때, 그 순서열(Sequence)이 서로 동일하다는 것을 의미합니다. 리프 노드: 자식 노드가 없는 노드를 말합니다. 예시 1: 입력: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8] Tree 1: Tree 2: 3 3 / \ / \ 5 1 5 1 / \ / \ / \ / \ 6 2 9 8 6 7 4 2 / \ / \ 7 4 9 8 출력: true 설명: Tree 1의 리프 노드 값 시퀀스: [6, 7, 4, 9, 8] Tree 2의 리프 노드 값 시퀀스: [6, 7, 4, 9, 8] 두 시퀀스가 동일하므로 두 트리는 Leaf-Similar 합니다. 예시 2: 입력: root1 = [1, 2, 3], root2 = [1, 3, 2] 출력: false 설명: Tree 1의 리프 노드 값 시퀀스: [2, 3] Tree 2의 리프 노드 값 시퀀스: [3, 2] 두 시퀀스가 다릅니다. 🤔 풀이 아이디어: DFS로 리프 노드 시퀀스 추출 후 비교 두 트리가 "Leaf-Similar"한지 확인하려면, 각 트리의 리프 노드 값들을 왼쪽에서 오른쪽 순서대로 추출하여 만들어진 시퀀스를 비교해야 합니다. 이를 위해 다음과 같은 단계를 따를 수 있습니다. 리프 노드 시퀀스 추출: 각 트리에 대해 깊이 우선 탐색(DFS)을 수행하여 모든 노드를 방문합니다. DFS 과정 중, 현재 방문한 노드가 리프 노드인지 확인합니다. (즉, 왼쪽 자식과 오른쪽 자식이 모두 없는지 확인) 만약 리프 노드라면, 그 노드의 값을 별도의 리스트(예: leaves)에 순서대로 추가합니다. DFS를 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 진행하면 자연스럽게 리프 노드들이 왼쪽에서 오른쪽 순서로 리스트에 담기게 됩니다. 시퀀스 비교: 첫 번째 트리(root1)에 대해 DFS를 수행하여 리프 노드 시퀀스(leaves1)를 얻습니다. 두 번째 트리(root2)에 대해 DFS를 수행하여 리프 노드 시퀀스(leaves2)를 얻습니다. 두 리스트 leaves1과 leaves2가 ...

🚀 문제: 104. Maximum Depth of Binary Tree 플랫폼: LeetCode 번호: 104 제목: Maximum Depth of Binary Tree 링크: https://leetcode.com/problems/maximum-depth-of-binary-tree/ 난이도: Easy 📝 문제 설명 주어진 이진 트리(Binary Tree)의 최대 깊이(Maximum Depth)를 구하는 문제입니다. 이진 트리의 최대 깊이는 루트 노드(root node)에서 가장 멀리 떨어져 있는 리프 노드(leaf node)까지의 경로 중에서 가장 긴 경로에 포함된 노드의 개수로 정의됩니다. 리프 노드: 자식 노드가 없는 노드를 의미합니다. 예시 1: 입력: root = [3, 9, 20, null, null, 15, 7] 3 / \ 9 20 / \ 15 7 출력: 3 설명: 루트(3)에서 가장 먼 리프 노드(15 또는 7)까지의 경로는 3개의 노드를 포함합니다. 예시 2: 입력: root = [1, null, 2] 출력: 2 🤔 풀이 아이디어: 재귀 (Recursive Approach) 이 문제는 트리의 구조적 특징을 활용하여 재귀(Recursion)적으로 접근하는 것이 매우 자연스럽습니다. 트리의 최대 깊이는 다음과 같은 재귀적인 관계로 생각할 수 있습니다. 기저 조건 (Base Case): 만약 현재 보고 있는 노드가 없다면 (root == None), 그 지점에서의 깊이는 0입니다. 더 이상 내려갈 경로가 없기 때문이죠. 재귀 단계 (Recursive Step): 만약 현재 노드가 있다면 (root != None), 이 노드를 포함한 트리의 최대 깊이는 다음과 같습니다: 왼쪽 서브트리의 최대 깊이를 재귀적으로 계산합니다 (maxDepth(root.left)). 오른쪽 서브트리의 최대 깊이를 재귀적으로 계산합니다 ...

🚀 문제: 724. Find Pivot Index 플랫폼: LeetCode 번호: 724 제목: Find Pivot Index 링크: https://leetcode.com/problems/find-pivot-index/description/ 난이도: Easy 📝 문제 설명 주어진 정수 배열 nums에서 피벗 인덱스(pivot index)를 찾는 문제입니다. 피벗 인덱스란, 해당 인덱스를 기준으로 왼쪽에 있는 모든 요소들의 합과 오른쪽에 있는 모든 요소들의 합이 정확히 같은 지점의 인덱스를 말합니다. 만약 피벗 인덱스가 여러 개 있다면, 가장 왼쪽에 있는 인덱스를 반환해야 합니다. 피벗 인덱스를 찾을 수 없다면 -1을 반환합니다. 배열의 양쪽 끝에서는 다음과 같이 간주합니다: 가장 왼쪽 인덱스(0)의 왼쪽 합은 0입니다. 가장 오른쪽 인덱스(n-1)의 오른쪽 합은 0입니다. 예시 1: 입력: nums = [1, 7, 3, 6, 5, 6] 출력: 3 설명: 인덱스 3 (값 6)을 기준으로 왼쪽 합(1 + 7 + 3 = 11)과 오른쪽 합(5 + 6 = 11)이 같습니다. 예시 2: 입력: nums = [1, 2, 3] 출력: -1 설명: 피벗 인덱스가 존재하지 않습니다. 예시 3: 입력: nums = [2, 1, -1] 출력: 0 설명: 인덱스 0을 기준으로 왼쪽 합은 0, 오른쪽 합은 1 + (-1) = 0입니다. 🤔 풀이 아이디어: 왼쪽 합과 오른쪽 합 추적하며 비교 이 문제는 배열을 순회하면서 각 인덱스가 피벗 인덱스의 조건을 만족하는지 확인하는 방식으로 접근할 수 있습니다. 제가 사용한 핵심 아이디어는 현재 인덱스를 기준으로 왼쪽 요소들의 합(left_sum)과 오른쪽 요소들의 합(right_sum)을 계속해서 업데이트하고 비교하는 것입니다. 초기값 설정: left_sum: 인덱스 0의 왼쪽에는 요소가 없으므로 0으로 시작합니다. right_sum: 인덱스 0의 오른쪽에 있는 모든 요소들의 합으로 시작합니다. (즉, nums[1]부터 끝까지의 합) 첫 번째 인덱스(0) 확인: 계산된 초기 left_sum과 right_sum이 같은지 확인합니다. 만약 같다면 인덱스 0이 피벗이므로 바로 0을 반환합니다. 인덱스 이동 및 합 업데이트: while 루프를 사용하여 인덱스 i를 0부터 n-2까지 증가시킵니다. (여기서 n은 배열의 길이입니다.) 루프의 각 단계에서는 다음 ...

🚀 문제: 1732. Find the Highest Altitude 플랫폼: LeetCode 번호: 1732 제목: Find the Highest Altitude 링크: https://leetcode.com/problems/find-the-highest-altitude/ 난이도: Easy 📝 문제 설명 자전거 운전자가 n+1개의 지점을 거치는 여행을 합니다. 여행은 고도 0에서 시작합니다. 정수 배열 gain이 주어지는데, gain[i]는 i번째 지점과 i+1번째 지점 사이의 순 고도 변화량을 의미합니다 (0≤i<n). 이 여행에서 도달하는 가장 높은 고도를 찾아 반환하는 문제입니다. 예시: 입력: gain = [-5, 1, 5, 0, -7] 출력: 1 설명: 각 지점에서의 고도는 [0, -5, -4, 1, 1, -6] 순서로 변합니다. 이 중 가장 높은 고도는 1입니다. 🤔 풀이 아이디어: 누적 합 (Prefix Sum) 이 문제는 각 지점의 고도를 계산하여 그중 최댓값을 찾는 문제입니다. 각 지점의 고도는 시작 고도(0)부터 해당 지점까지의 고도 변화량을 계속 더해나가면 구할 수 있습니다. 이것이 누적 합(Prefix Sum)의 기본 아이디어입니다. 배열 준비: 고도 변화량(gain)을 저장할 배열(arr)과 각 지점에서의 누적 고도를 저장할 배열(p_Sum)을 준비합니다. 배열 크기는 총 지점의 수(n+1)에 맞춰줍니다. p_Sum[0]은 시작 고도인 0으로 초기화됩니다. 누적 고도 계산: gain 배열의 값을 순서대로 arr 배열에 옮겨 담으면서, p_Sum 배열을...