pjaehyun의 개발일지

문제

https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/

You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.

Return the maximum possible length of s.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

문자열로 이루어진 배열 arr이 주어질 때, 요소들을 합쳐서 만들 수 있는 가장 긴 문자열을 반환해라. 

문자열을 합쳤을 때 중복되는 문자가 존재하면 안된다.

Example 1:

Example 2:

Example 3:

문제풀이 코드

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        result = [""]
        for i in range(len(arr)):
            if len(arr[i]) > len(set(arr[i])): continue
            for j in range(len(result)):
                temp = result[j] + arr[i]
                if len(temp) == len(set(temp)):
                    result.append(temp)
        result.sort(key=lambda x:len(x))
        return len(result[-1])

1. 빈 문자열이 들어있는 배열을 선언한다.

2. 주어진 arr을 순회하면서 현재 문자열에 중복된 문자열이 존재하면 continue

3. 그렇지않을 때, result를 순회하면서 result[j] + arr[i]를 해준다.

4. 만약 두 단어를 더했을 때 중복된 문자가 존재하면 result에 넣어주지않는다.

5. result를 문자열의 길이로 정렬하고 가장 긴 문자열을 반환한다.

문제

https://leetcode.com/problems/assign-cookies/description/

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example 1:

Example 2:

문제풀이 코드

첫번째 풀이

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        result = 0
        for i in range(len(g)):
            j = 0
            find = False
            while j < len(s):
                if g[i] > s[j]:
                    j += 1
                else:
                    result += 1
                    s = s[j+1:]
                    find = True
                    break
            if not find:
                return result
        return result

1. g와 s를 오름차순으로 정렬한다

2. j = 0, find = False로 초기화하고 g[i]와 s[j]를 비교

3. while문을 돌면서 g[i]가 s[j]보다 클 때 j = j + 1을 하고

4.g[i]가 s[j]보다 작거나 같을 때 result = result + 1을 하고 s = s[j+1:]을 해준다.(j = 0 부터 시작하기때문에 s를 계속 초기화해줌)

5. while문을 다돌고 find가 False라면 현재 result값을 반환하고 

6. 모든 반복문이 종료되면 result를 반환한다

두번째 풀이(시간복잡도 개선)

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i, j, result = 0, 0, 0

        while i < len(g) and j < len(s):
            if g[i] <= s[j]:
                i, result = i + 1, result + 1
            j = j + 1
        return result

1. g[i]가 s[j]보다 작을때만 i = i + 1, result = result + 1을 해주고 (쿠키의 크기가 아이가 쿠키를 원하는 크기보다 클때)

2. j는 항상 j + 1을 해준다

3. 반복문이 끝나면 result를 반환한다

문제

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

Example 1:

Example 2:

Example 3:

문제풀이 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        queue = deque()
        queue.append((root, 0))
        result = []
        while queue:
            node, level = queue.popleft()
            if node == None: continue
            if node.left != None: queue.append((node.left,level + 1))
            if node.right != None: queue.append((node.right,level + 1))

            try:
                result[level].append(node.val)
            except:
                result.append([])
                result[level].append(node.val)
        return result[::-1]

BFS로 문제 접근(같은 레벨에 있는 노드들을 탐색하기때문)

1. 노드를 삽입하는 큐에는 노드와 현재 레벨이 들어갈 수 있도록 튜플로 삽입한다.

2. 현재 노드를 탐색한 후에 left가 None이 아닐 때 (node.left, level+1)를 큐에 삽입한다.

3. 현재 노드를 탐색한 후에 right가 None이 아닐 때 (node.right, level+1)를 큐에 삽입한다.

4. 큐에 삽입한 후 result[level]이 없으면 result에 추가해주고 현재 노드를 resule[level]에 추가한다.

5. 아래에서부터 탐색한 결과를 반환해야하기 때문에 result를 뒤집어서 반환한다.

문제

https://leetcode.com/problems/binary-tree-inorder-traversal/

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

Example 2:

Example 3:

문제풀이 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        def inOrder(root):
            if not root:
                return
            inOrder(root.left)
            result.append(root.val)
            inOrder(root.right)
        inOrder(root)
        
        return result

기본적인 트리 순회 문제 (중위 순회)

1. 순회를 돌면서 결과를 담는 result를 만든다

2. 중위 순회 함수를 재귀적으로 호출하면서 result에 순서에 맞게 결과값을 담는다

3. 재귀함수가 모두 호출된 후 결과를 반환한다

문제

https://leetcode.com/problems/3sum/

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = set()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i-1] == nums[i]:
                continue
            j = i + 1
            k = len(nums) - 1
            while j < k:
                if nums[i] + nums[j] + nums[k] > 0:
                    k -= 1
                elif nums[i] + nums[j] + nums[k] < 0:
                    j += 1
                else:
                    result.add((nums[i],nums[j],nums[k]))
                    while j < k and nums[j] == nums[j+1]:
                        j+=1
                    while j < k and nums[k] == nums[k-1]:
                        k-=1
                    j += 1
                    k -= 1
        return [list(x) for x in result]

투포인터 방식으로 문제접근

1. 투포인터를 사용하기위해 nums를 오름차순으로 정렬해준다

2. 반복문을 돌면서 i,j 또는 k를 조건에 맞게 계산해준다.

  (1). i값이 0보다 크고 현재 값이 이전값과 동일하면 continue를 해준다(안해주면 이전과 같은 일을 반복해서 느려짐)

  (2). nums[i] + nums[j] + nums[k] > 0일 때는 합을 줄여줘야하기 때문에 k = k-1을 해준다

  (3). nums[i] + nums[j] + nums[k] < 0일 때는 합을 키워야하기 때문에 j = j+1을 해준다

  (4). nums[i] + nums[j] + nums[k] == 0일 때 세개의 수를 집합에 담아준다(중복을 피하기위함)

        - 현재의 값과 그다음값 또는 현재의 값과 그 이전값이 동일할 수 있어 현재와 다른 값이 나올 때 까지 j=j+1, k=k-1

          을 해준다(없어도 통과는 되지만 시간복잡도가 마지막에 겨우 걸쳐짐)

문제

https://leetcode.com/problems/largest-perimeter-triangle/

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

정수로 이루어진 배열 nums가 주어질때 넓이가 0이 아닌 삼각형의 가장 큰 둘레를 반환해라.

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        for i in range(len(nums)-2):
            if nums[i] < nums[i + 1] + nums[i + 2]:
                return nums[i] + nums[i + 1] + nums[i + 2]
        return 0

세 개의 변을 알고있을 때 삼각형의 결정조건으로 문제 풀이(가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야한다)

1. nums를 내림차순으로 정렬한다

2. nums[i]와 nums[i + 1] + nums[i + 2]를 비교하여 참이되면 현재 값을 반환한다

3. 루프가 끝나도 종료되지않으면 0을 반환한다

문제

https://leetcode.com/problems/increasing-triplet-subsequence/description/

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Example 1:

Example 2:

Example 3:

문제풀이 코드

첫번째 코드

# 첫번째 코드 (Time Limit Exceeded) 완전탐색
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        for i in range(len(nums) - 2): 
            for j in range(i+1, len(nums) - 1):
                if nums[i] < nums[j] and nums[j] < max(nums[j+1:]):
                    return True
        return False

1. 반복문 두개를 사용하여 i, j, j+1을 각각 비교하면서 결과를 찾는다.

2. 시간복잡도 O(n^2)으로 시간초과

두번째 코드

# 해법이 생각이 나지않아 Solution 참고
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        i, j = float('inf'), float('inf')
        for k in nums:
            if k > j: return True  
            if k <= i: i = k 
            else: j = k      
        return False

1. k가 i보다 작거나 같을 때 i=k
2. j는 i보다 무조건 크기때문에 i는 i보다 작거나 같은값으로 바뀌어도된다.

3. k는 j보다 무조건 크기때문에 j는 j보다 작거나 같은값으로 바뀌어도된다.
4. k가 j보다 크면 i < j < k가 성립하게 된다.

문제

https://leetcode.com/problems/break-a-palindrome/

Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.

1. 영어 소문자로 이루어진 palindromic 문자열이 주어진다.

2. 해당 문자열의 문자하나를 바꾸어 palindrome이 안되도록 바꾸고, 사전순으로 가능한 작은 문자열이 되도록 한다.

3. 문자를 바꿀 방법이 존재하지 않으면 빈 문자열을 반환한다.

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        palindrome = list(palindrome)
        if len(palindrome) == 1:
            return ""
            
        for i in range(len(palindrome) // 2):
            if palindrome[i] != 'a':
                palindrome[i] = 'a'
                return ''.join(palindrome)
        palindrome[-1] = 'b'
        return ''.join(palindrome)

그리디 알고리즘으로 문제 접근

1. palindrome특성상 앞뒤가 같은 문자니까 반복문은 2로 나눈만큼 돌아도 된다.

2. 문자를 변경했을 때 사전순으로 가능한 작게 만들기위해선 'a'로 치환하면 된다.

3. 모든 문자가 'a'일 때 마지막문자를 'b'로 바꿔주면된다.