새싹프로그래머의 이야기

[풀이 방법]

• 그래프 탐색을 통해 무인도를 탐색해준다.
• 리스트 내의 값들이 string 형태이므로 list로 변환하여 사용하면 더 편하다.
• 탐색 함수 안에서 조건문을 통해 list의 Index를 벗어나지 않도록 설정해준다.
• 파이썬은 재귀함수의 깊이를 제한하므로 반복문을 통해 문제를 해결하거나, sys함수를 통해 깊이를 늘려줘야한다.

*이러한 문제 종류들을 만날 때, 항상 많이 헤메었었다. 리스트 내의 값을 확인 해야할 때는 '그래프 탐색'을 먼저 떠올릴 수 있으면 좋을 것 같다.

[풀이 코드]

import sys

sys.setrecursionlimit(1000000)


def search(maps, row, column, visited, value):
    if (row, column) in visited or 0 > row or row > len(maps) - 1 or column < 0 or column > len(maps[0]) - 1 or \
            maps[row][column] == 'X':
        return value
    value += int(maps[row][column])
    visited.append((row, column))
    value = search(maps, row - 1, column, visited, value)
    value = search(maps, row + 1, column, visited, value)
    value = search(maps, row, column - 1, visited, value)
    value = search(maps, row, column + 1, visited, value)

    return value


def solution(maps):
    answer = []
    visited = []
    maps = [list(Amap) for Amap in maps]
    value = 0

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 'X' or (i, j) in visited:
                continue
            answer.append(search(maps, i, j, visited, value))

    return sorted(answer) if answer else [-1]

[풀이 방법]

• List로 귤의 크기가 주어졌을 때, 최소한의 귤의 종류로 판매하고 싶은 갯 수를 채워야 하므로 Counter 함수를 통해 귤 크기 별로 갯 수를 구해준다.
• 최소한의 종류로 판매하고자 하는 갯 수를 채우기 위해서는 갯 수가 많이 들어있는 크기의 귤을 활용하여 채워줘야 한다. 따라서, Counter의 most_common() 함수를 통해 정렬하여 문제 조건을 만족하는 귤 종류의 갯 수를 구한다.

[풀이 코드]

from collections import Counter


def solution(k, tangerine):
    answer = 0
    dic = Counter(tangerine)

    for i in dic.most_common():
        answer += 1
        k -= i[1]
        if k <= 0:
            break

    return answer

C언어를 사용할 때는 malloc() 함수와 free()함수를 통해 메모리를 직접 할당/해제를 해주었습니다. 

그런데 Python을 사용할 때는 별도로 메모리를 관리하지 않더라구요.

문득 왜일까? 라는 생각이 들어서 알아보고 정리를 해보려고 합니다.

Python의 메모리 관리

파이썬은 Garbage Collector가 메모리를 관리해줍니다. C언어와 달리 사람이 메모리를 직접 할당/해제 하는 것이 아니라 언어 자체에서 직접 관리해주는 방식인데요. 

가장 많이 활용하는 방식은 Reference Counting 이라는 방식입니다.

Reference Counting 이란?

Reference Counting 방식이란, 객체를 얼마나 참조하는지를 통해 메모리를 관리하는 방식입니다.

Python은 객체를 생성하면 Heap 메모리에 객체를 생성하는데요. 

예를 들어, 다음과 같은 코드가 있을 때 s라는 변수가 객체를 참조하는 것을 counting 하여 메모리를 관리합니다.

s = 'hello world'

위와 같은 코드를 작성하면 다음과 같이 변수가 객체를 참조하게 됩니다.

'hello world'라는 객체를 s에 할당했을 때, Garbage Collector는 'hello world'라는 객체의 reference counting을 1 증가시키고 메모리에 할당합니다.

반대로 s라는 변수가 다른 객체를 참조하게 되었을 때는 reference counting이 0이 될 것이고 Garbage Collector는 이를 통해 메모리를 해제하게 됩니다.

직접 확인해보면 다음과 같습니다.

s가 호출된 함수가 종료되면 reference counting은 0이 되어 메모리는 해제되게 됩니다.

Garbage Collector의 장점 및 단점

사람이 직접 관리하지 않아도 메모리 관리가 되기 때문에 편하지만, 장점만 존재하는 것은 아닙니다.

Garbage Collector의 장점이라 함은 다음과 같습니다.

• reference counting이 0 이 될 때마다 메모리를 해제해주기 때문에 실시간 작업이 가능하다.
• 위와 같은 이유로 메모리 관리가 간편하며 즉시 메모리에서 해제가 가능하다.

반면 단점 또한 존재합니다.

• Object 마다 reference counting을 수행해주어야 하기 때문에 관리 비용이 많이 듭니다.
• Object의 reference count가 0이 될 경우, 연쇄적인 Garbage Collecting이 발생할 수 있습니다.
• 사람이 직접 할당/해제를 하지 않기 때문에 세밀한 메모리 관리가 어렵다.

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/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 자체를 활용하여 연산하는 것이 더 좋다는 것을 알 수 있습니다.