leetcode.com 763. Partition Labels

문제 링크: https://leetcode.com/problems/partition-labels/description/

파이썬 소스: https://bit.ly/48LfUEP

스트링 s에서 첫 글자를 때서, 2개의 리스트로 나눠 보겠습니다.

s[:1] , s[1:]으로 나누고, 2개의 리스트를 set()으로 변환한 뒤에, intersection() 메서드로 공통된 원소가 있는지에 확인해 봅니다. s[:1]의 길이가 1이기 때문에, intersection()의 리턴값인 set의 길이는 1또는 0 입니다. 코드로 구현하면 아래와 같습니다.

set_part = set(s[:1]) set_right = set(s[1:]) intersection = set_part.intersection(set_right)

 

-      Intersection의 길이가 0 이라는 의미는 s[1:] 과 s[:1]사이에 같은 원소가 없다는 뜻 입니다. 따라서, 1이 partition할 위치가 됩니다.

-      반대로 1이라는 의미는 s[:1]과 같은 글자가 s[1:]안에 포함되어 있다는 의미입니다. 문제에 따라서, parts as possible so that each letter appears in at most one part. 이 문장대로, 하나의 파트에 최대한 같은 글자가 많이 들어 있도록 partition을 해야 합니다. 그러므로, s[1:]과 같은 글자가 s[1:]에 들어 있기 때문에, 인덱스 2를 확인해 봐야 합니다.

 

s의 길이로 루프를 만들고, 파티션에 포함될 부분을 set_part = set()로, 파티션에 포함되지 않을 부분을 set_right = set(s[i:])로 아래와 같이 구현합니다. 두 set 사이에 intersection이 0이면 파티션을 나눠야 하구요, 0 보다 크다면, 파티션의 크기를 더 크게 할 수 있습니다.

 

from typing import List class Solution:     def partitionLabels(self, s: str) -> List[int]:         set_part = set()         partition_length = 0         answer = []         for i in range(len(s)):             if len(set_part) > 0:                 set_right = set(s[i:])                 intersection = set_part.intersection(set_right)                 if len(intersection) == 0:                     set_part.clear()                     answer.append(partition_length)                     partition_length = 0             set_part.add(s[i])             partition_length += 1         if partition_length != 0:             answer.append(partition_length)         return answer

 

코데풀 유튜브 구독 부탁드립니다.
https://www.youtube.com/@codapul

 

leetcode.com 1899. Merge Triplets to Form Target Triplet

문제 링크: https://leetcode.com/problems/merge-triplets-to-form-target-triplet/description/

파이썬 소스: https://bit.ly/3TcXcQy

​

Triplet, 즉 3개의 원소를 가지는 리스트에 처음부터 너무 관심을 두면 풀기 어려운 문제입니다.

간단하게 triplet의 첫번째 원소만 생각해 보겠습니다.

Example 1번을 보면, 3개의 triplet이 입력으로 주어집니다. 3개 모두 0번째 원소만 뽑아 보겠습니다. 2, 1, 1 입니다. Max(2, 1, 1)을 해보면, target[0] 과 같습니다.

즉, 3개의 원소, 2, 1, 1 모두 target[0] 보다 작거나 같기 때문에, merge할 수 있습니다.

즉, target[x] 보다 크다면, merge 할 수 없으므로, 아래와 같이 비교 할 수 있습니다.

if not (t[0] > target[0] or t[1] > target[1] or t[2] > target[2]):

 

t 는 입력으로 주어지는 triplet 리스트 입니다. Triplet의 한 원소라도, target 보다 크다면 merge 할 수 없습니다.

전체 코드는 아래와 같습니다. 마지막에 return 을 할 때, target의 각 원소가, dt0~2에 모두 있는지 and로 확인합니다. dt0에는 target[0] 보다 작거나 같은 원소가 들어 있습니다. Target[0]가 dt0 안에 포함되어 있다면, 첫번째 자리는 target[0] 값이 될 수 있습니다.

 이와 같이 두번째, 세번째 자리까지 and로 검사하면, 이문제의 답을 구할 수 있습니디.

코데풀 유튜브 구독 부탁드립니다.
https://www.youtube.com/@codapul

 

from typing import List class Solution:     def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:         dt0 = []         dt1 = []         dt2 = []         for t in triplets:             if not (t[0] > target[0] or t[1] > target[1] or t[2] > target[2]):                 dt0.append(t[0])                 dt1.append(t[1])                 dt2.append(t[2])         return target[0] in dt0 and target[1] in dt1 and target[2] in dt2

 

leetcode.com 53. Maximum Subarray

 문제 링크: https://leetcode.com/problems/maximum-subarray/description/

파이썬 소스: https://bit.ly/4caMLWo

 

 우선 nums와 길이가 같은 dp 리스트를 하나 만들어 줍니다. 이후에 설명하겠지만, max() 함수를 사용해서, dp 리스트에 값을 어싸인할 것이므로, 모두 최소값(이문제에서는 10**4 -1)으로 초기화 해줍니다.

음수와 양수가 서로 섞여 있는 상태에서 가장큰 부분합을 가지는 subarray의 합을 찾는 문제입니다. 문제의 초점을 헷갈릴 수 있어서, 다시한번 정리하면, Subarrary를 찾는 문제가 아니라, 가장 큰 부분합을 찾는 문제입니다.

Subarray가 가장 큰 부분합을 가지려면, 가장 작은 subarray인 길이가 2인 subarray에 대해서 먼저 알아보겠습니다.

 여기서, 나를 최대합이 되고 싶은 dp 리스트에 있는 하나의 원소라고 가정합니다.

그러면, dp[0]인 나는 nums[0] 이 됩니다. 나의 왼쪽에 아무도 없기 때문입니다.

이제 나는 dp[1] 입니다. 나의 왼쪽에 있는 친구를 더해서, 나는 최대합이 되고 싶습니다.

dp[1] = max(nums[1], dp[0] + nums[1])

 

dp[1]에 대해서 코드로 작성해 보면 위와 같습니다. 이 코드를 인덱스 i 에 대해서 작성해보겠습니다.

for i in range(1, len(nums)):     dp[i] = max(nums[i], dp[i-1] + nums[i])

 

이 문제를 풀 때, 주의 할 점은, 최대 합을 구하는 것이지, 최대 합을 가지는 구간을 구하는 문제가 아닙니다.

즉, dp 리스트에 있는 각 아이템들이, 나의 왼쪽을 더할 것인지 아닌지를 판단하면, 자연스럽게 최대합을 구할 수 있습니다.

 

from typing import List class Solution:     def maxSubArray(self, nums: List[int]) -> int:         dp = [-1 * (10 ** 9) -1] * len(nums)         dp[0] = nums[0]         for i in range(1, len(nums)):             dp[i] = max(nums[i], dp[i-1] + nums[i])         return max(dp)

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul