LeetCode 문제 풀이: 46. Permutations (순열)

🚀 문제: 605. Can Place Flowers 플랫폼: LeetCode 번호: 605 제목: Can Place Flowers 링크: https://leetcode.com/problems/can-place-flowers/ 난이도: Easy 📝 문제 설명 정수 배열 flowerbed가 주어집니다. 이 배열에는 0과 1이 들어있는데, 1은 꽃이 이미 심어져 있는 칸을 의미하고 0은 비어있는 칸을 의미합니다. 또한, 정수 n이 주어집니다. 꽃은 인접한 두 칸에 동시에 심을 수 없습니다. 즉, 어떤 칸에 꽃을 심으면 그 바로 왼쪽 칸과 바로 오른쪽 칸에는 꽃을 심을 수 없습니다. flowerbed에 n개의 새로운 꽃을 심을 수 있으면 true를, 없으면 false를 반환하세요. (배열의 경계를 넘어서는 것은 고려하지 않습니다. 즉, flowerbed[0]의 왼쪽이나 flowerbed[length-1]의 오른쪽에는 아무것도 없다고 가정합니다.) 예시 1: 입력: flowerbed = [1,0,0,0,1], n = 1 출력: true 설명: 가운데 0에 꽃 하나를 심을 수 있습니다. 예시 2: 입력: flowerbed = [1,0,0,0,1], n = 2 출력: false 설명: 하나의 꽃만 심을 수 있으므로 두 개는 불가능합니다. 🤔 풀이 아이디어: 비어있는 공간을 찾아 꽃 심기 제가 사용한 풀이 아이디어는 flowerbed를 문자열로 변환한 후, 1(이미 꽃이 심어진 곳)을 기준으로 나누어(split) 비어있는 공간(0들의 연속)을 찾는 것입니다. 그리고 각 비어있는 공간의 특성(맨 앞인지, 맨 뒤인지, 중간인지)에 따라 몇 개의 꽃을 심을 수 있는지 계산합니다. 특별 케이스: 꽃밭에 꽃이 하나도 없는 경우 (flowerbed.count(1) == 0) 만약 flowerbed에 1이 하나도 없다면, 모든 칸이 비어있습니다. 이 경우, 심을 수 있는 꽃의 개수는 (배열의 길이 + 1) // 2가 됩니다. (예: [0,0,0] (길이 3) -> (3+1)//2 = 2개) 이 값이 n보다 크거나 같으면 True를 반환합니다. 일반 케이스: 꽃밭에 꽃이 하나 이상 있는 경우 flowerbed 배열을 문자열로 변환합니다. (예: [0,0,1,0,1] -> "00101") 이 문자열을 "1"을 기준으로 분리하여 연속된 "0" 문자열들의 리스트를 얻습니다. (예: "00101" -> ["00", "0", ""]) flowerbed의 시작과 끝이 0인지 아닌지에 따라 4가지 경우로 나누어 처리합니다. 시작은 0, 끝은 0이 아님 (예: [0,0,1,0,1]): 맨 앞의 연속된 0들(parts[0])에는 len(parts[0]) // 2개의 꽃을 심을 수 있습니다. 나머지 중간의 연속된 0들(parts[1:]의 빈 문자열이 아닌 요소)에는 (len(w) - 1) // 2개의 꽃을 심을 수 있습니다. 시작은 0이 아님, 끝은 0 (예: [1,0,1,0,0]): 맨 뒤의 연속된 0들(parts[-1])에는 len(parts[-1]) // 2개의 꽃을 심을 수 있습니다. 나머지 중간의 연속된 0들(parts[:-1]의 빈 문자열이 아닌 요소)에는 (len(w) - 1) // 2개의 꽃을 심을 수 있습니다. 시작과 끝 모두 0 (예: [0,0,1,0,0]): 맨 앞(parts[0])과 맨 뒤(parts[-1])의 연속된 0들에는 각각 길이 // 2개의 꽃을 심을 수 있습니다. 그 사이의 연속된 0들(parts[1:-1]의 빈 문자열이 아닌 요소)에는 (len(w) - 1) // 2개의 꽃을 심을 수 있습니다. 시작과 끝 모두 0이 아님 (즉, 양 끝이 1이거나 단일 1 등) (예: [1,0,0,1]): 모든 연속된 0들(parts의 빈 문자열이 아닌 요소)은 1과 1 사이의 공간이므로, (len(w) - 1) // 2개의 꽃을 심을 수 있습니다. 최종 확인: 위에서 계산된 총 심을 수 있는 꽃의 개수(place)를 구합니다. place가 n보다 크거나 같으면 True를, 아니면 False를 반환합니다. 이 아이디어의 핵심은 "1이 없는 경우"라는 엣지 케이스를 먼저 처리하고, 그 외의 경우에는 배열의 양 끝 상태에 따라 split된 조각들을 다르게 해석하여 계산하는 것입니다. 💻 코드 (Python) 제가 직접 작성한 코드입니다. Python from typing import List class Solution: def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool: place = 0 # 1. flowerbed에 '1'이 하나도 없는 경우 (가장 먼저 처리하는 엣지 케이스) if flowerbed.count(1) == 0: # 모든 칸이 0이므로, (길이+1)//2 만큼 심을 수 있음 if (len(flowerbed)+1) // 2 >= n: return True else : return False # 아래는 flowerbed에 '1'이 하나 이상 있는 경우들입니다. # flowerbed의 시작과 끝이 0인지 여부에 따라 4가지 경우로 나눕니다. # 2-1. 시작은 0, 마지막은 0이 아닌 경우 (예:...

🚀 문제: 1431. Kids With the Greatest Number of Candies 플랫폼: LeetCode 번호: 1431 제목: Kids With the Greatest Number of Candies 링크: https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/ 난이도: Easy 📝 문제 설명 n명의 아이들이 있고, 각 아이가 가진 사탕의 수를 나타내는 정수 배열 candies가 주어집니다. candies[i]는 i번째 아이가 가진 사탕의 수입니다. 또한, 정수 extraCandies가 주어지는데, 이는 추가로 나눠줄 수 있는 사탕의 총 개수입니다. 각 아이에 대해, 만약 그 아이에게 extraCandies 만큼의 사탕을 모두 주었을 때, 그 아이가 다른 모든 아이들 중에서 가장 많은 사탕을 가지게 되는지 (또는 같아지는지) 판별해야 합니다. 여러 아이가 가장 많은 사탕을 가질 수 있습니다. 결과로 각 아이에 대해 위의 조건을 만족하면 true, 아니면 false를 담은 boolean 배열을 반환해야 합니다. 예시 1: 입력: candies = [2, 3, 5, 1, 3], extraCandies = 3 출력: [true, true, true, false, true] 설명: 아이 1: 2 + 3 = 5개. 현재 최댓값 5와 같으므로 true. 아이 2: 3 + 3 = 6개. 현재 최댓값 5보다 크므로 true. 아이 3: 5 + 3 = 8개. 현재 최댓값 5보다 크므로 true. 아이 4: 1 + 3 = 4개. 현재 최댓값 5보다 작으므로 false. 아이 5: 3 + 3 = 6개. 현재 최댓값 5보다 크므로 true. 예시 2: 입력: candies = [4, 2, 1, 1, 2], extraCandies = 1 출력: [true, false, false, false, false] 설명: 아이 1에게만 추가 사탕을 주었을 때 가장 많은 사탕을 가지게 됩니다. 🤔 풀이 아이디어: 최대 사탕 수와 비교 이 문제는 각 아이가 추가 사탕을 받았을 때, 그 수가 현재 아이들 중 가장 많은 사탕 수보다 크거나 같은지를 ...

🚀 문제: 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)). 오른쪽 서브트리의 최대 깊이를 재귀적으로 계산합니다 ...