새싹프로그래머의 이야기

https://leetcode.com/problems/minimum-absolute-difference-in-bst/

문제: 트리의 노드의 중에서 두 노드의 차가 제일 작은 값을 구하는 문제

풀이 코드:

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        tree = []

        def getVal(root: Optional[TreeNode]):
            tree.append(root.val)
            if root.left != None:
                getVal(root.left)
            if root.right != None:
                getVal(root.right)

        getVal(root)

        tree = sorted(tree)

        return min(tree[i + 1] - tree[i] for i in range(len(tree) - 1)) 

777번: https://leetcode.com/problems/swap-adjacent-in-lr-string/

2337번: https://leetcode.com/problems/move-pieces-to-obtain-a-string/

문제: 'L' 과 'R' 이 포함된 두 문자열이 주어졌을 때, 문제에서 목표로 주어진 문자열을 만들 수 있는지 여부를 판별하는 문제

문제 설명:

두 문제 모두, 'L' 이라는 문자는 왼쪽으로만 이동 가능하며, 'R'이라는 문자는 오른쪽으로만 이동 가능하도록 되어있습니다.

이때 각 문자는 서로를 넘어갈 수 없습니다.

예를 들면, '_L_RR' 이라는 문자가 주어졌을 때, 'L__RR'은 만들 수 있지만 '__RLR'은 만들 수 없습니다.

풀이 코드:

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        if start.replace('_', '') != target.replace('_', ''):
            return False

        startL = [i for i in range(len(start)) if start[i] == 'L']
        startR = [i for i in range(len(start)) if start[i] == 'R']
        endL = [i for i in range(len(target)) if target[i] == 'L']
        endR = [i for i in range(len(target)) if target[i] == 'R']

        for i, j in zip(startL, endL):
            if i < j:
                return False

        for i, j in zip(startR, endR):
            if i > j:
                return False
        return True

풀이의 핵심은 두가지 입니다.

• 'L'과  'R'의 순서는 바뀔 수 없음
• 목표 문자열에서 기존 문자열 대비 'L'의 위치는 오른쪽에 존재할 수 없으며, 반대로 'R' 의 위치 또한 왼쪽에 존재 할 수 없다는 것입니다.

if start.replace('_', '') != target.replace('_', ''):
    return False

공백에 해당하는 문자열을 없앤 후, 두 문자열을 비교하여 순서를 확인합니다.

startL = [i for i in range(len(start)) if start[i] == 'L']
startR = [i for i in range(len(start)) if start[i] == 'R']
endL = [i for i in range(len(target)) if target[i] == 'L']
endR = [i for i in range(len(target)) if target[i] == 'R']

for i, j in zip(startL, endL):
    if i < j:
        return False

for i, j in zip(startR, endR):
    if i > j:
        return False

위 코드를 통해, 'L'과 'R'의 위치 변화를 판별합니다.

*풀이는 Discuss에서 투표를 많이 받은 풀이를 참조하였습니다.

https://leetcode.com/problems/watering-plants/

문제: 들고 다닐 수 있는 물의 양과 각 식물에 필요한 물의 양이 주어질 때, 모든 식물에 물을 주기 위해 이동해야하는 거리를 구하는 문제.

문제 설명:

우물은 index가 -1에 해당하는 위치에 있다고 가정을 하며, 각 식물이 필요로 하는 물의 양은 1차원 배열로 주어지고 한번에 들고 다닐 수 있는 물의 양은 int형으로 주어집니다.

위 예시를 한번 보면, 총 4개의 식물에 물을 주어야하며 들고 다닐 수 있는 물의 용량은 5입니다.

index가 0에 해당하는 식물에 도달하여 물을 주면, 이동 거리는 1이 되며 남은 물의 용량은 3이 됩니다.

index가 1에 해당하는 식물에 도달하여 물을 주면, 이동거리는 2가 되며 남은 물의 용량은 1이 됩니다.

이때, 다음 식물은 3만큼의 물의 양이 필요한데 현재 가지고 있는 물의 양은 1이므로 우물에 다녀와야 합니다.

따라서, 2칸 뒤로 이동해 물을 채운 후 다음 식물에 해당하는 위치로 이동해 물을 주어야 합니다.

이 과정을 반복하여 모든 식물에 물을 주는데 필요한 거리를 구하는 문제 입니다.

풀이 코드:

class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        now = -1
        steps = 0
        cap = capacity
        for i in range(len(plants)):
            steps += (i - now)
            cap -= plants[i]
            now = i
            if i != len(plants) - 1 and cap < plants[i + 1]:
                steps += (i + 1) * 2
                cap = capacity

        return steps

문제에서는 위의 예시에서 index = 1 인 위치에서 물을 채워오는 거리를 2칸 뒤로 간 후, 다음 위치인 index = 2인 위치로 3칸 앞으로 이동하는 계산 방식을 사용했습니다.

하지만 저는 우물에 들려 물을 채운 후 index = 2인 위치로 향할 때, index = 1인 위치에서 index = -1 로 왕복을 한 후 앞으로 1칸 전진하는 계산 방식을 사용했습니다.

https://leetcode.com/problems/add-two-numbers/

문제: 수를 역순으로 구성한 두 개의 linked-list가 존재할 때, 각 linked-list의 자리 수를 더한 결과 값을 구하는 문제

문제 설명:

문제에서 주어진 예시를 보면 다음과 같습니다.

342 는  2 -> 4 -> 3 으로 구성되며, 465는 5 -> 6 -> 4로 구성됩니다.

각 자리 수의 합을 구하면 807로 7 -> 0 -> 8로 구성된 linked-list를 반환하면 됩니다.

문제 코드:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        number1 = 0
        ten1 = 1
        number2 = 0
        ten2 = 1

        while True:
            number1 += (l1.val * ten1)
            if l1.next == None:
                break
            l1 = l1.next
            ten1 *= 10
        while True:
            number2 += (l2.val * ten2)
            if l2.next == None:
                break
            l2 = l2.next
            ten2 *= 10

        linked_list = None

        for i in list(str(number1 + number2)):
            cur = ListNode()
            cur.val, cur.next = i, linked_list
            linked_list = cur
        return linked_list

저 같은 경우, 각 linked-list의 값을 10진수로 변환한 후 더한 값을 구해 다시 liked-list를 구성하는 방식을 사용했습니다.

다른 풀이 코드를 보다 linked-list 자체로 풀이를 진행한 깔끔한 코드가 있어 소개해보고자 합니다.

그 코드는 다음과 같습니다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        val = 0
        head = ListNode()
        linked_list = head
        while l1 or l2 or val:

            if l1:
                val += l1.val
                l1 = l1.next
            if l2:
                val += l2.val
                l2 = l2.next

            linked_list.next = ListNode(val % 10)
            linked_list = linked_list.next
            val //= 10

        return head.next

linked-list에서 10진수로의 변환을 하지 않고 문제를 푼 코드입니다.

제 코드의 경우, Runtime은 151ms이고 메모리는 14.1MB를 사용했습니다.

제가 추가로 올려드린 코드의 경우 Runtime은 120ms이고 메모리는 13.8MB를 사용했습니다.

시간과 공간 활용도 모두 linked-list 자체를 활용하여 연산하는 것이 더 좋다는 것을 알 수 있습니다.

https://leetcode.com/problems/defuse-the-bomb/

문제: 문제에서 주어진 조건에 따라, 배열 원소의 합을 반환하는 문제

문제 설명:

정수가 담긴 배열과 k라는 값이 주어집니다.

다음과 같이 총 3가지 조건에 따라 문제를 풀이하는 방법이 달라집니다. 

• k > 0 일 경우, 배열의 i번째 값은 i번째 이후 k개의 원소의 합으로 대체됩니다.

예를 들어, [5, 7, 1, 4] 이라는 배열과 k = 3 이라는 값이 주어질 경우, 0번째는 7+1+4 (==12) 로 대체되고 1번째 값은 1+4+5(==10)으로 대체됩니다.

따라서 최종 반환되는 배열은 [12, 10, 16, 13] 이 됩니다.

• k < 0 일 경우, 배열의 i번째 값은 i번째 이전 k개의 원소의 합으로 대체됩니다.

예를 들어, [2, 4, 9, 3] 이라는 배열과 k = -2 라는 값이 주어질 경우, 0번째는 3+9 (==12)로 대체 되고 1번째 값은 2+3 (==5)로 대체됩니다.

따라서 최종 반환되는 배열은 [12, 5, 6, 13] 이 됩니다.

• 마지막으로 k = 0 일 경우, 배열의 모든 원소는 0이 되어 반환됩니다.

풀이 코드:

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        length = len(code)
        lst = []
        if k > 0:
            for i in range(length):
                s = 0
                for j in range(1, k + 1):
                    s += code[(i + j) % length]
                lst.append(s)

        elif k < 0:
            for i in range(length):
                s = 0
                for j in range(1, abs(k) + 1):
                    s += code[i + (-1 * j)]
                lst.append(s)
        else:
            return [0] * length
        return lst

https://leetcode.com/problems/unique-number-of-occurrences/

문제: 숫자로 이루어진 배열에서 각 원소의 갯수가 중복되는지 판별하는 문제

문제 설명:

문제에서 주어진 예시로 설명을 해보겠습니다.

예제 1번을 보면, [1, 2, 2, 1, 1, 3] 이라는 배열이 있습니다.

원소 1은 3개, 원소 2는 2개, 원소 3은 1개로 각 원소의 갯수가 중복되지 않으므로 True를 반환해줍니다.

예제 2번을 보면, 원소 1과 2가 둘다 1로 원소의 갯수가 중복이 되므로 False를 반환해줍니다.

저는 이 문제를 파이썬의 Counter 함수를 통해서 풀었는데, Counter 함수를 사용하게 되면 다음과 같은 결과가 나옵니다

from collections import Counter
arr= [1,2,2,1,1,3]
print(Counter(arr))

# 출력한 결과
# Counter({1: 3, 2: 2, 3: 1})

Counter를 쓰면 key-value 쌍으로 counter 형의 데이터가 만들어집니다.

이를 바탕으로, value 값들을 통해 중복된 값이 있는지 여부를 판별해주었습니다.

풀이 코드:

from collections import Counter
from collections import deque


class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        cntarr = Counter(arr)
        counterval = deque(cntarr.values())

        while counterval:
            v = counterval.pop()
            if v in counterval:
                return False
        return True