# Word Pattern

[Quetion]

LeetCode 290. Word Pattern

📌 접근법

[문제 이해]

• 주어진 pattern과 문자열의 패턴이 같으면 True 아니면 False

• ex) pattern = abba, s = dog cat cat dog

가장 먼저 문자열 구분하기 위해서는 공백을 기준으로 split()하고 pattern을 key 값, value를 문자열로 하는 HashMap의 방법으로 접근했다.

HashMap에서 이미 key가 있으면 반복되는 패턴임을 확인할 수 있고, key의 value와 문자열을 비교하면 패턴이 맞는지 확인하는 조건문으로 구현을 했다.

💻 구현

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        word = s.split(' ')
        w_dict = {}
        # 패턴의 길이와 문자열의 길이 비교
        if len(pattern) != len(word):
            return False

        for i, d in enumerate(pattern):
            # pattern에 해당하는 key가 있을 경우 key와 분리된 문자열 비교  
            if d in w_dict and w_dict[d] != word[i]:
                return False

            # key가 없는데 문자열이 HashMap에 있는 경우      
            elif d not in w_dict and word[i] in w_dict.values():
                return False

            # pattern을 key, 분리된 문자열을 value로 하는 HashMap 값 생성
            elif d not in w_dict:
                w_dict[d] = word[i]
        return True 

Runtime: 26ms | Memory: 16.2MB LeetCode 코드 중 Runtime 99%, Memory 85% 해당하는 결과

📌 로직 핵심

• 문자열 s를 공백 기준으로 분리
• enumerate()로 인덱스와 값을 동시에 활용 가능
• pattern을 key로 하고 분리된 문자열을 value로 하는 HashMap
• False의 경우를 분리
• 반복문 내의 조건이 모두 아닌 경우 True

📝 Word Pattern 회고

• 문자열을 분리하는 과정에서 O(N)의 시간복잡도가 발생했고, 모든 문자열이 독립적일 경우 딕셔너리에 문자열 전부를 저장해야하므로 최악의 경우 O(N)의 공간복잡도를 가진다.

• HashMap의 key:value로 바로 접근할 수 있다는 특성을 활용한 간단한 문제였다.

• 문제를 해결하고 솔루션을 참고했을 때 dict를 2개 사용한 코드도 있었고, dict를 사용하지 않은 코드들도 있었다. 그리고 거의 같은 방법으로 접근하여 해결한 코드도 있었다.

• 크게 어려운 문제는 아니었지만 응용되는 문제가 나왔을 때 다른 자료구조와 함께 HashMap의 방법을 잘 사용하는 것이 중요할 것 같다고 생각했다.

# Same Tree

[Quetion]

LeetCode 100. Same Tree

📌 접근법

[문제 이해]

• 두 Binary Tree p와 q가 같은지 확인

두 binary tree가 같은 형태, 같은 값을 가지는지 확인하기 위해서는 모든 노드를 순회해야한다고 생각했고, DFS와 BFS 중 BFS의 방법으로 접근했다.

p와 q를 순회하며 노드의 값을 저장하고, 만약 트리의 형태가 다르면 (ex: p는 왼쪽 q는 오른쪽에 하위 트리가 구성 되어있는 경우) 순회 결과를 다르게 하기 위해 0을 추가로 삽입했다.

💻 구현

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # p와 q가 모두 None이거나 한쪽만 None일 경우
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False

        p_tree,q_tree=[],[]
        self.level_search(p, p_tree)  
        self.level_search(q, q_tree)
        return p_tree == q_tree

    # BFS
    def level_search(self, node, l):
        queue = [(node, 0)]
        while queue:
            node, level = queue.pop(0)
            if node is not None:
                l.append(node.val)
                if node.left:
                    queue.append((node.left, level+1))
                if node.right:
                    queue.append((node.right, level+1))
                else:
                    l.append(0)

Runtime: 32ms | Memory: 16.1MB LeetCode 코드 중 Runtime 90%, Memory 94% 해당하는 결과

📌 로직 핵심

• p와q 트리를 각각 BFS로 순회
• node.left가 있고, node.right가 있는 조건과 더불어 0값을 추가하여 하위 트리 형태가 다르면 순회 결과를 다르게 하여 T or F 판단

📝 Same Tree 회고

• 모든 트리를 순회하고 마지막으로 두 리스트를 비교하기에 최악의 경우 O(N) 시간복잡도를 가지고, 방문한 노드의 값을 모두 저장해야하므로 O(N)의 공간복잡도를 가진다.

• 시간복잡도는 BFS, DFS 모두 모든 노드를 순회하기 때문에 O(N)으로서, 이미 최적화가 되었다고 생각하고 공간복잡도는 p_tree와 q_tree 리스트를 제거하는 방향으로 개선할 수 있을 것 같다.

  # 개선 후
  class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
  
        queue = [(p, q)]
        while queue:
            np, nq = queue.pop(0)
            if np is None and nq is None:
                continue
  
            elif np is None or nq is None or np.val != nq.val:
                return False
  
            queue.append((np.left, nq.left))
            queue.append((np.right, nq.right))
        return True

시간복잡도와 공간복잡도는 여전히 O(N)으로 변함이 없지만 두 리스트를 제거함으로써 메모리에 할당되는 것을 줄였다.

코드도 더 간단해졌지만 while문 내부의 조건문이 길어져서 가독성은 떨어질 수 있겠다고 생각했다.

메모리적으로 더 유리할 수 있지만 개인적으로 개선한 코드보다는 함수로 작성한 이전 로직이 보기에도 편하고, 비즈니스 로직이라고 생각했을 때, 유지보수성이 더 높을 것 같다고 판단된다.

# Merge k Sorted Lists

[Quetion]

LeetCode 23. Merge k Sorted Lists

📌 접근법

[문제 이해]

• 이중 리스트 구조로 된 연결 리스트를 모두 합치고, 오름차순 정렬된 연결 리스트로 반환

[[1,4,5],[1,3,4],[2,6]]로 이루어진 연결리스트를 1->1->2->3->4->4->5->6로 반환 해야하는 문제이다. 가장 먼저 떠올린 접근방법은 다음과 같다.

• 포인터를 이동하며 이중 리스트 구조에 접근
• 연결 리스트의 값을 배열에 저장
• 값이 저장된 배열을 sorted()로 정렬
• 정렬된 배열을 기준으로 연결 리스트 생성

💻 구현

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 연결 리스트의 값 저장
        link=[]
        # 이중 리스트에 접근할 포인터
        i=0
        while len(lists)-1 >= i:
            if lists[i]:
                link.append(lists[i].val)
            else:
                i+=1
                continue
            lists[i]=lists[i].next

        # O(N log N) 정렬
        link=sorted(link)

        # 연결 리스트 생성
        result=ListNode()
        curr=result
        for i in link:
            node=ListNode(i)
            curr.next=node
            curr=node
        return result.next

Runtime: 75ms | Memory: 19.8MB LeetCode 코드 중 Runtime 99%, Memory 81% 해당하는 결과

📌 로직 핵심

• lists = [[1,4,5],[1,3,4],[2,6]]일때, i 포인터로 lists[i]에 접근 ex)(lists[0]=[1,4,5])
• lists[i].next로 1->4->5 접근, 만약 lists[i]가 None일 경우, i 포인터의 값 증가 = 다음 리스트를 가리키고 다시 다음 리스트의 첫 값을 가리키도록 continue로 반복문 제어
• 병합 정렬 기반 sorted()함수로 오름차순 정렬
• 정렬된 리스트로 새로운 연결 리스트 생성

📝 Merge k Sorted Lists 회고

• 시간복잡도는 이중 연결리스트의 모든 값을 조회하므로 O(N)이 되고, 처음 연결 리스트의 값 개수 만큼 다시 새로운 연결 리스트를 생성하므로 O(N)의 공간복잡도를 가진다.

• 이중 리스트 구조에서 첫번째 리스트를 첫번째 하위 연결 리스트로 생각한다면, 재귀와 분할정복의 개념으로도 문제를 해결할 수 있을 것 같다. 하지만 성능적으로 봤을 때는 비슷하게 나올거라 예상된다.

• 문제 해결 후 솔루션을 확인해보니 heap 자료구조를 활용해서 문제를 해결할 수도 있었고, 코드는 더 간결하지만 현재 사용한 접근법과 유사한 방법으로 해결한 문제도 꽤 많았다.

• 추가적으로 연결 리스트를 생성하고, 서로 연결해주는 과정을 조금 더 간단하게 개선해보았다.

  class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        link=[]
        i=0
        while len(lists)-1 >= i:
            if lists[i]:
                link.append(lists[i].val)
            else:
                i+=1
                continue
            lists[i]=lists[i].next
  
        link=sorted(link, reverse=True)
        result=None
        for i in link:
            result=ListNode(i, result)
        return result

성능은 비슷한 것으로 확인했고, 정렬된 값으로 새로운 노드를 생성할 때 next 값을 result로 해줌으로써 역순으로 연결이 된다.예를들어 [1,2,3,4,5,6]의 값으로 정렬되어 있으면 연결 리스트는 6->5->4->3->2->1 로 생성된다.

따라서 기존 sorted() 함수로 오름차순 정렬 해주었던 연결 리스트의 값을 내림차순 정렬로 변경하여 1->2->3->4->5->6이 될 수 있도록 구현했다.

난이도가 Hard로 표기 되어있지만 연결 리스트 문제들을 경험하고 응용함으로써 비교적 수월하게 문제를 해결한 것 같다.

# Insert Delete GetRandom O(1)

[Quetion]

LeetCode 380. Insert Delete GetRandom O(1)

📌 접근법

[문제 이해]

• 문자열 삽입, 삭제, 랜덤 조회 함수 만들기

• 평균 O(1)의 시간복잡도
• 이미 문자열이 있을 때 삽입시 False
• 문자열이 없을 때 삭제시 False

O(1)의 시간복잡도로 접근하기 위해서는 Hashmap을 활용해야 겠다고 생각했다.

문자열이 없을 때 삭제시 False를 반환하는 것은 stack을 구현할 때의 stack underflow가 떠올랐다.

💻 구현

class RandomizedSet:
    def __init__(self):
        self.ran_set=[]
        self.ran_hash={}

    def insert(self, val: int) -> bool:
        if val in self.ran_hash.keys():
            return False
        else:
            self.ran_hash[val]=None
            self.ran_set.append(val)
            return True

    def remove(self, val: int) -> bool:
        try:
            del self.ran_hash[val]
            self.ran_set.remove(val)
            return True
        except KeyError:
            return False

    def getRandom(self) -> int:
        return random.choice(self.ran_set)

Runtime: 349ms | Memory: 63.5MB LeetCode 코드 중 Runtime 53%, Memory 95% 해당하는 결과

📌 로직 핵심

• ran_hash 딕셔너리에 데이터를 key 값으로 저장
• in 연산자로 이미 key가 있는지 확인
• try except 구문으로 딕셔너리에 key 값이 없는 경우 처리
• random.choice() 라이브러리 및 함수로 동일 확률 랜덤하게 원소 조회

📝 Insert Delete GetRandom O(1) 회고

• 시간복잡도는 O(1), 공간복잡도는 O(N)이 나왔다.

• dictionary.get('key')로 key값이 없으면 None으로 확인가능 했지만 key가 있음에도 None이 출력되는 상황을 발견해서 try except 구문으로 KeyError를 응용하여 구현했다.

• 리스트와 딕셔너리를 모두 사용하며 삽입, 삭제하기 때문에 조금 비효율적이라고 생각해서 set()의 특징을 활용하여 개선해보았다.

  class RandomizedSet:
    def __init__(self):
        # ran_hash를 중복이 없는 집합으로 선언
        self.ran_hash=set()
  
    def insert(self, val: int) -> bool:
        if val in self.ran_hash:
            return False
        self.ran_hash.add(val)
        return True
  
    def remove(self, val: int) -> bool:
        if val in self.ran_hash:
            self.ran_hash.remove(val)
            return True
        return False
  
    def getRandom(self) -> int:
        return random.choice(list(self.ran_hash))

• Runtime*: 349ms ---> 493ms

• Memory*: 63.5MB ---> 63.7MB

코드는 간결해졌지만 list, hashmap 두 가지를 모두 활용한 방법보다 오히려 성능적으로 떨어지게 되었다.

list(self.ran_hash)로 집합을 list로 변환하는 과정에서 O(N)의 시간복잡도가 되었고, 평균적으로 시간복잡도가 증가하여 더 좋지 못한 성능이 나온 것 같다.

그래서 Hashmap만 활용하여 구현을 해보았지만 set()과 마찬가지로 getRandom()함수에서 O(N)의 시간복잡도가 걸렸다.

결과적으로 처음 작성한 코드가 성능적으로는 가장 우수했다는 것을 알았고, 대부분의 솔루션 코드도 같은 방법으로 접근한 것을 확인했다.

# Single Number

[Quetion]

LeetCode 58. Length of Last Word

📌 접근법

[문제 이해]

• 문자열 s의 하위 문자열에서 마지막 하위 문자열(단어)의 길이

• hello world --> world : 5 출력

문자열 s에서 공백이 있는 경우도 있을 것이기 때문에 strip()함수를 활용해서 해결해야겠다고 생각했다.

간단한 문제이기 때문에 2가지의 접근 방법으로 접근 해보았다.

• 첫번째는 split()으로 s를 공백으로 분리하여 해결
• 두번째는 문자열을 역순으로 반복하여 판단하는 것으로 해결

💻 구현

# 첫번째 split() 활용
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s=s.rstrip().split(' ')
        return len(s[-1])

Runtime: 26ms | Memory: 16.3MB LeetCode 코드 중 Runtime 99%, Memory 72% 해당하는 결과

# 두번째 반복문 활용
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s=s.strip()
        i=1
        while len(s)>i:
            if s[-i] == ' ':
               return i-1
            i+=1  
        return i

Runtime: 28ms | Memory: 16.1MB LeetCode 코드 중 Runtime 97%, Memory 99% 해당하는 결과

📌 로직 핵심

• strip(), rstrip() 함수의 활용으로 문자열에서 공백 제거
• 첫번째는 공백으로 분리하여 마지막 단어를 쉽게 찾음
• 두번째는 마지막 단어와 그 이전 단어와의 공백을 활용하여 찾음
• 두번째에서 i는 마지막과 그 이전 단어와의 공백을 가리키므로 -1을 해줌으로써 마지막 단어의 처음을 가리키게 됨

📝 Length of Last Word 회고

• 두 방법 모두 시간복잡도는 O(N), 공간복잡도는 O(1)에 해당하는 결과이다.

• 성능적으로는 두 코드 모두 유사하다고 할 수 있다. 하지만 python 함수를 아는 경우, 코드 가독성과 간결성은 첫번째 코드가 더 좋다고 판단된다.

• 문제를 해결하고 다른 솔루션들을 참고해보니 대부분 첫번째 코드의 방법으로 접근하여 해결했지만, 두번째 접근법과 유사한 코드도 확인했다.

• 문자열을 다루는 문제는 다른 복잡한 자료구조 문제와는 달리 접근 방법이 더 다양한 것 같다고 생각된다.

# Single Number

[Quetion]

LeetCode 136. Single Number

📌 접근법

[문제 이해]

• nums 리스트에서 중복되지 않는 값 1개 찾기

큰 주제가 비트를 조작하여 문제를 풀어보라는 의도 같았지만, 다른 접근법으로도 좋은 성능으로 해결할 방법이 떠올라서 비트연산이 아닌 다른 방법으로 풀어보았다.

값들끼리 중복이 되는지 원할하게 판단하기 위해서는 중복되는 값끼리 붙어 있으면 편하다고 생각했다. 그래서 오름차순 정렬을 하고 두개의 포인터로 창문(sliding window)을 만들어서 창문을 이동시키는 방법으로 접근했다.

💻 구현

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 오름차순 정렬
        nums = sorted(nums)
        i,j=0,1

        # 두 포인터를 이동
        while len(nums) > j:
            if nums[i] != nums[j]:
                return nums[i]
            i+=2
            j=i+1
        return nums[i]

Runtime: 120ms | Memory: 18.8MB LeetCode 코드 중 Runtime 77%, Memory 86.2% 해당하는 결과

📌 로직 핵심

• sorted()로 오름차순 정렬하여 중복된 수는 함께 붙어있도록 설계
• 포인터 2개로 창문을 만들어서 옮겨줌으로써 중복 판단 ex) [0,1], [2,3], [4,5] 등
• 창문 속 수가 다르면 중복이 되지 않는다고 판단
• [1,1,2,2,3]일 경우 창문은 항상 [2,2]까지만 이동, 나머지 수는 중복되지 않는다고 판단

📝 Single Number 회고

• 시간복잡도는 sorted() 과정에서 가장 많은 시간이 걸려서 O(N log N)이고, 공간복잡도는 O(1)으로 상수의 공간복잡도를 가진다.

• 문제를 해결하고 다른 솔루션들을 찾아보니 대부분 XOR 연산을 활용하여 매우 간단하게 문제를 해결했고, 코드는 다음과 같다.

  class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        num = 0
        for i in nums:
            num ^= i
        return num

  num에 XOR 연산을 수행한 결과를 저장하고 갱신하는 방법이다. 예를 들어 [4,1,2,1,2]의 nums를 for문을 실행하면 num은 4,5,7,6,4의 결과로 최종 4가 출력된다.

하지만 해당 방법의 시간복잡도는 nums를 모두 순회해야 하기 때문에 O(N)의 시간복잡도를 가진다. 따라서 코드 간결성은 좋지만 성능상으로는 원래 작성한 코드가 더 좋을 수도 있기에 따로 변경하지는 않았다.

# Binary Tree Level Order Traversal

[Quetion]

LeetCode 102. Binary Tree Level Order Traversal

📌 접근법

[문제 이해]

• Binary Tree를 레벨 별로 노드 값을 리스트에 담아 반환

레벨 별로 노드 값을 알아야하기 때문에 Binary Tree BFS(너비 우선 탐색)를 활용하여 접근했다. BFS 방법으로 순회하며 결과 리스트에 레벨 별로 리스트를 생성하고, 노드의 값을 추가해주는 법으로 구현했다.

💻 구현

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        l=[]
        self.level_search(root, l)
        return l

    # BFS
    def level_search(self, node, l):
        queue = [(node, 0)]
        while queue:
            node, level = queue.pop(0)
            if node is not None:
                if len(l) < level+1:
                    l.append([])   
                l[level].append(node.val)
                if node.left:
                    queue.append((node.left, level+1))
                if node.right:
                    queue.append((node.right, level+1))

Runtime: 40ms | Memory: 16.8MB LeetCode 코드 중 Runtime 84%, Memory 99.7% 해당하는 결과

📌 로직 핵심

• BFS 함수 생성, 재귀 활용하여 Left, Right Tree 탐색
• Queue 자료구조를 활용하여 방문처리
• level 변수를 활용하여 레벨 별 리스트에 바로 접근하여 노드의 값 추가

📝 Binary Tree Level Order Traversal 회고

• 모든 트리를 순회하고, 결과 리스트에 레벨 별로 노드 값을 모두 저장해야하므로 시간복잡도와 공간복잡도 모두 O(N)이다.

• BFS 방법을 활용하여 레벨 별로 노드 값을 저장하는 간단한 응용 문제여서 비교적 쉽게 해결했다.

• BFS를 활용한 637. Average of Levels in Binary Tree를 먼저 해결해서 비교적 더 쉬웠던 것 같다.

• 문제를 해결하고 다른 솔루션을 보니 대부분 현재 코드와 비슷한 방식으로 해결해 나간 것을 확인했다. 그리고 특별한 추가적인 개선은 떠오르지 않아서 다른 수정은 진행하지 않았다.

# Reverse Words in a String

[Quetion]

LeetCode 151. Reverse Words in a String

📌 접근법

[문제 이해]

• 문자열을 단어 단위로 거꾸로 뒤집기

• ex) " hello world " ---> "world hello"
• 단어는 공백으로 분리, 문자열들의 맨 앞, 맨 뒤의 공백은 제거

단어가 공백을 기준으로 분리되어 있으므로 split()함수를 활용하여 공백 기준으로 분리하고, 스택의 원리를 활용하여 문자열을 뒤집는 접근법으로 생각했다.

💻 구현

class Solution:
    def reverseWords(self, s: str) -> str:
        s=s.split(' ')
        r=''
        while s:
            if s[-1] != '':
                r=r+s.pop()+' '
            else:
                s.pop()
        # 양쪽 공백 제거
        r=r.strip()
        return r

Runtime: 28ms | Memory: 16.2MB LeetCode 코드 중 Runtime 98%, Memory 99% 해당하는 결과

📌 로직 핵심

• split() 함수로 공백 기준 분리
• 분리한 문자열이 담긴 리스트를 POP 하여 결과 문자열에 공백과 함께 더해가기
• 빈 값 (공백)일 경우 pass
• strip()함수로 제거되지 않은 문자열 양 끝단의 공백 제거

📝 Reverse Words in a String 회고

• 시간복잡도는 O(N)이지만 공간복잡도는 r에 더해가는게 전부이기 때문에 O(1)을 가진다.

• split()으로 분리된 문자열을 다른 리스트에 추가하는 방법으로도 쉽게 해결이 가능한 문제지만 그렇게 할 경우, 공간복잡도는 O(N)이 되므로 현재 방법을 선택했다.

• while문을 탈출하게 되면 ' abc def ' 에서 'def abc '가 되어 문자열 끝 부분에는 공백이 남게된다. 이를 해결하기 위해 양 끝단의 공백을 제거해주는 strip() 함수를 사용하므로써 간편하게 해결했다.

# Simplify Path

[Quetion]

LeetCode 71. Simplify Path

📌 접근법

[문제 이해]

• unix 스타일 절대경로를 표준경로로 변환

• 경로는 / 로 시작
• / 으로 끝나지 않아야 함
• 디렉토리는 / 로 구분되어야 함
• . or ..는 경로에 미포함

stack의 LIFO 특성을 활용하여 디렉토리의 문자열만 Push하고 /를 배치해주는 방법으로 접근했다.

• path 경로를 / 기준으로 분리 (split 함수 사용)
• 분리한 경로 만큼 반복
• 빈 값 or .이면 pass
• ..인 경우 POP
• 이외(디렉토리 문자열)에는 Push
• 스택에 있는 문자열 앞과 문자열 사이에는 / 삽입

💻 구현

class Solution:
    def simplifyPath(self, path: str) -> str:
        # stack
        result=[]

        # /로 경로 문자열 분리
        path = path.split('/')
        for i in path:
            # 빈 값 pass
            if i == '':
                continue

            # ..일 경우 POP, stack != None
            elif i == '..':
                if result != []:
                    result.pop()

            # . pass, 문자열 PUSH
            elif i != '.':
                result.append(i)

        # '/' 삽입 
        return '/'+'/'.join(result)

Runtime: 38ms | Memory: 16.1MB LeetCode 코드 중 Runtime 76%, Memory 97% 해당하는 결과

📌 로직 핵심

• /로 경로 문자열 분리함으로써 //같은 문자열 PUSH 상황 삭제
• ..일 경우 Stack Underflow 방지를 위해 result가 None이 아닌 상황에만 POP
• '/'.join 연산으로 디렉토리 문자열 사이에 /추가, '/'+'/'로 경로 a/b 앞에 /추가

📝 Simplify Path 회고

• 시간복잡도와 공간복잡도는 모두 O(N)이다.

• 스택의 LIFO 특성을 응용하는 간단한 문제였다. 처음에는 path를 그대로 반복하며 if문과 함께 push와 pop을 진행했다. 하지만 코드가 복잡했고 //이 섞이면서 뜻대로 되지않았다.

• 그래서 /기준으로 문자열을 분리해보았고, if문의 경우의 수도 줄어들며 join 연산을 통해 간편하게 /을 추가 할 수 있어서 문제를 해결할 수 있었다.

• 문제를 해결하고 다른 솔루션들을 보아도 같은 방법으로 접근한 코드들이 많았다는 것을 확인하며 간단한 문제일수록 생각이 비슷하다는 것을 느낄 수 있었다.

# Find First and Last Position of Element in Sorted Array

[Quetion]

LeetCode 34. Find First and Last Position of Element in Sorted Array

📌 접근법

[문제 이해]

• 오름차순으로 정렬된 배열에서 target값의 시작점과 끝나는 지점을 반환

• target 값이 없는 경우 [-1, -1] 반환
• O(log N)의 시간복잡도

O(log N)의 시간복잡도이기 때문에 이진탐색의 방법으로 접근해야한다. 처음 지점을 가리키는 l 포인터, 끝 지점을 가리키는 r 포인터를 활용하여 다음과 같이 생각했다.

• l <= r 만큼 반복
• mid = (l+r)//2 일때 nums[mid]가 target보다 크면 r 포인터를 mid - 1로 옮긴다.
• 반대면 l 포인터를 mid + 1로 옮긴다.
• 만약 nums[l]이 target과 같지 않으면 l포인터를 1씩 증가시킨다.
• nums[r]이 target과 같지 않으면 r 포인터를 1씩 증가시킨다.
• nums[l]이 가리키는 값과 nums[r]이 가리키는 값이 target과 일치하면 l, r을 반환

💻 구현

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l,r = 0, len(nums)-1
        while l <= r:
            mid = (l+r)//2 
            if nums[l] == nums[r] == target:
                return [l, r]
            # 중앙값이 target 보다 크고 작은 경우 l, r 옮김
            if nums[mid] > target:
                r = mid - 1 
            if nums[mid] < target:
                l = mid + 1
            # l과 r 포인터 1칸씩 이동
            else:
                if nums[l] != target:
                    l += 1
                if nums[r] != target:
                    r -= 1
        return [-1, -1]

Runtime: 78ms | Memory: 17.7MB LeetCode 코드 중 Runtime 87%, Memory 90% 해당하는 결과

📌 로직 핵심

• 중앙값과 target값 비교상황 이외에도 l과 r 포인터를 1칸씩 이동
• l과 r이 가리키는 값이 target 값과 같으면 l, r이 target의 시작과 끝점을 가리키는 것

📝 Find First and Last Position of Element in Sorted Array 회고

• 시간복잡도는 이진검색을 활용하여 O(log N)이고, 공간복잡도는 O(1)을 가진다.

• 처음에는 일반적인 이진검색 알고리즘을 활용하여 중앙값에 따라 l과 r 포인터만 움직였지만 틀렸었다.

• 그래서 중앙값과 target의 비교 이외에도 l과 r이 가리키는 값을 각각 target과 비교함으로써 l, r의 포인터를 한 칸씩 움직이는 것을 추가했다.

• 더 이상 어떻게 성능적으로 개선해 볼 수 있을지는 떠오르지 않아서 코드 수정은 하지 않았다.

• 문제를 해결하고 다른 솔루션을 보니 재귀를 활용한 코드가 간단해서 인상 깊었다. 그리고 현재 코드와 동일한 방법으로 해결한 코드들이 많았던 것을 확인할 수 있었다.

# Remove Duplicates from Sorted List II

[Quetion]

LeetCode 82. Remove Duplicates from Sorted List II

📌 접근법

[문제 이해]

• 주어진 링크드 리스트에서 중복되는 노드는 전부 삭제한 후 링크드 리스트 반환

• ex) [1-2-3-3-4] ---> [1-2-4]

조금 복잡하지만 내가 생각한 구현 흐름은 다음과 같다.

• Linked List의 데이터인 val을 리스트에 모두 담는다.
• 리스트에 담긴 값을 key, 중복되는 개수를 value로 하는 HashTable 생성
• HashTable에서 value가 1 초과인 key는 모두 삭제
• 남아있는 key를 다시 리스트에 담고, 리스트 값을 기준으로 링크드 리스트로 변환

💻 구현

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # num에 Linked List 데이터 담기
        num=[]
        while head:
            num.append(head.val)
            head = head.next

        # num 값을 key, 중복 개수를 value로 하는 dict 
        num_dict={}
        for i in num:
            num_dict[i] = num_dict.get(i, 0) + 1

        # value > 1인 key 삭제
        duplicate = [key for key, value in num_dict.items() if value > 1]
        for i in duplicate:
            del num_dict[i]

        # key 기준 다시 리스트로 변경, 링크드 리스트로 재생성
        num = [i for i in num_dict.keys()]
        result = ListNode()
        curr = result
        i=0
        while len(num) > i:
            node = ListNode(num[i])
            curr.next = node
            curr = node
            i+=1
        return result.next

Runtime: 42ms | Memory: 16.2MB LeetCode 코드 중 Runtime 80%, Memory 78% 해당하는 결과

📌 로직 핵심

• Linked List 데이터를 추출
• HashTable 활용 중복 데이터 제거
• 다시 Linked List로 재생성

📝 Remove Duplicates from Sorted List II 회고

• 시간복잡도와 공간복잡도는 모두 O(N)이다. 반복문이 많이 사용되긴 했지만, 최대 Linked List의 Node 개수 만큼만 반복하므로 O(N)만큼의 시간복잡도와 공간복잡도가 나오게 된 것이다.

• 리스트에 데이터를 담는 과정과 dict를 생성하는 과정을 합칠 수 있고, 중복된 데이터를 삭제하고 다시 리스트로 바꾸지 않고도 Linked List로 변경할 수 있어서 코드를 조금 변경해보았다.

  # 수정된 코드
  class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        num_dict = {}
        while head:
            num_dict[head.val] = num_dict.get(head.val, 0) + 1
            head = head.next
  
        duplicate = [key for key, value in num_dict.items() if value > 1]
        for i in duplicate:
            del num_dict[i]
  
        result = ListNode()
        curr = result
        for i in num_dict:
            node = ListNode(i)
            curr.next = node
            curr = node
        return result.next

  성능상 큰 차이는 없지만 리스트에 Linked List의 데이터를 담는 과정을 삭제하고, key값을 리스트에 담는 과정을 줄임으로써 반복문 2개를 제거했다.

문제를 해결하고, 다른 솔루션을 찾아보니 재귀적으로 해결한 솔루션이 가장 신기하게 느껴졌고, HashTable 방법을 활용한 코드도 많다는 것을 알게 되었다.

아직 Linked List 자체를 조작하는 것에 익숙하지 않아서 더 어렵게 느껴지는 것 같다.

# Median of Two Sorted Arrays

[Quetion]

LeetCode 4. Median of Two Sorted Arrays

📌 접근법

[문제 이해]

• 두 리스트를 합쳤을 때 오름차순 정렬한 상태에서의 중앙값 반환

• O(log m+n)의 시간복잡도 제한

문제에서 요구한 대로 우선 두 리스트를 더하고, 병합정렬(O nlogn)기반의 sorted() 함수로 정렬하는 방법을 생각했다.

정렬한 리스트의 길이가 홀수일 경우 중앙값을 그대로 반환하고, 짝수이면 중앙값 2개의 평균을 계산하도록 했다.

💻 구현

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums=sorted(nums1+nums2)
        mid=len(nums)//2
        if len(nums)%2!=0:
            return nums[mid]
        else:
            return (nums[mid] + nums[mid-1])/2

Runtime: 81ms | Memory: 16.4MB LeetCode 코드 중 Runtime 93%, Memory 84% 해당하는 결과

📌 로직 핵심

• 병합정렬 기반의 sorted()함수로 오름차순 정렬

📝 Median of Two Sorted Arrays 회고

• 시간복잡도는 정렬과정에서 발생한 O(n log n)이고 공간복잡도는 O(1)이다.
• 난이도 Hard 문제였지만 내장 함수의 시간복잡도를 잘 알고 활용한다면 쉽게 접근이 가능한 문제였다.
• two pointer 방법과 분할정복의 개념으로 접근할 수도 있으나, 성능 차이는 거의 없다고 판단했고, 오히려 포인터 변수를 많이 할당하게 되어 메모리를 더 사용하며 코드 복잡도도 증가할 거라 생각했다.

# Maximum Depth of Binary Tree

[Quetion]

LeetCode 104. Maximum Depth of Binary Tree

📌 접근법

[문제 이해]

• 이진 트리의 깊이를 구하는 문제

깊이를 구하기 위해서는 깊이 우선 탐색(DFS) 방법으로 접근이 필요하다. DFS는 전위, 중위, 후위 방식이 있는데 이번에는 전위순회 방식을 활용했다.

• 현재 노드를 방문 처리하고 깊이를 저장
• 왼쪽 서브 트리를 방문 후 오른쪽 서브 트리를 방문하는 재귀호출
• 재귀 호출 전 깊이를 증가

💻 구현

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        depth=0
        result=[]
        self.preorder(root, depth, result)

        # depth가 담긴 리스트의 중복 제거와 정렬
        result=sorted(set(result))
        return result[-1]

    # 전위순회
    def preorder(self, root, depth, result):
        if root is None:
            result.append(depth)
            pass
        else:
            depth+=1
            self.preorder(root.left, depth, result)
            self.preorder(root.right, depth, result)

Runtime: 37ms | Memory: 18.6MB LeetCode 코드 중 Runtime 96%, Memory 74% 해당하는 결과

📌 로직 핵심

• 왼쪽과 오른쪽 서브트리를 순회하며 result 리스트에 깊이를 저장
• 저장된 깊이 중 중복을 제거하고 오름차순 정렬
• 값이 가장 큰 result의 마지막 값 반환

📝 Maximum Depth of Binary Tree 회고

• 시간복잡도는 N=트리 노드의 수 라고 할 때 전위순회 과정에서 O(N), 중복제거와 정렬과정에서 O(NlogN)이므로 O(N + NlogN) = O(NlogN)을 가진다.
• 공간복잡도는 최악의 경우 트리의 모든 리프노드의 깊이를 저장할 수 있으므로 O(N)이 된다.
• 다른 솔루션들을 참고해보니 단순 재귀의 방법으로 깊이를 구하고 max()함수로 최대 깊이를 구한 코드가 인상 깊었다.
• 솔루션을 참고하여 코드를 다시 변경해보았다.

  # 수정된 코드
  class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1

• Runtime*: 37ms ---> 43ms
• Memory*: 18.6MB ---> 18.5MB

성능상으로는 기존 코드와 크게 차이는 없는 코드이다. 하지만 코드가 훨씬 간결해졌고 Memory를 조금 더 개선할 수 있었다.

이번 문제를 해결하면서 느낀점은 아직 재귀가 익숙하지 않아서 그런지 탐색을 구현하는데 있어서 어려움이 있는 것 같다. 문제를 풀며 익숙해질 수 있도록 더 노력해야겠다 :D

# Longest Consecutive Sequence

[Quetion]

LeetCode 128. Longest Consecutive Sequence

📌 접근법

[문제 이해]

• 리스트 내에서 연속된 수의 최대 개수 반환

Hashmap을 활용하는 문제이지만 우선 바로 생각나는대로 풀어보았다. 생각의 흐름은 다음과 같다.

• nums 리스트의 중복을 제거
• 중복 제거한 nums 리스트를 정렬
• 리스트의 첫 값을 변수에 저장, 카운트 변수와 카운트 리스트 선언
• 리스트의 길이만큼 반복
• 저장한 변수 + 1이 다음 순서의 값과 같으면 카운트 + 1
• 아니면 카운트 리스트에 카운트 추가, 카운트 = 0
• 변수는 비교한 리스트 값으로 재정의

💻 구현

class Solution:
    def longestConsecutive(self, nums):
        # nums가 없으면 0
        if not nums:
            return 0

        # 중복제거 & 정렬
        nums = sorted(set(nums))
        n = nums[0]

        # 연속된 수의 개수 저장
        count = 0

        # 연속이 끊겼을 때, 연속되었던 수 저장
        max_c = []

        for i in range(1,len(nums)):
            if n+1 == nums[i]:
                count+=1
            else:
                max_c.append(count+1)
                count=0
            n = nums[i]

        max_c.append(count+1)
        max_c.sort()
        return max_c[-1]

Runtime: 335ms | Memory: 30.9MB LeetCode 코드 중 Runtime 99%, Memory 87% 해당하는 결과

📌 로직 핵심

• 주어진 리스트의 중복을 제거하고 정렬
• 연속되는지 확인 후 연속된 개수 세기
• 연속이 끊기면 현재까지 연속된 개수를 리스트에 저장
• 모두 연속된 경우를 대비하여 반복 후, 연속된 개수를 다시 추가
• 연속된 개수가 담긴 리스트를 정렬하면 가장 큰수는 마지막 값

📝 Longest Consecutive Sequence 회고

• 해당 코드의 시간복잡도는 nums의 중복을 제거하여 O(nlogn)이고 최악은 중복이 없는 경우의 O(N)이다. 공간복잡도는 중복을 제거후, 정렬된 새로운 리스트를 생성하는 과정에서 O(N)이다.

• 현재 코드에서는 max_c 리스트에 연속되는 개수를 저장하는 방법으로 최대 연속 개수를 판단하지만, max()함수를 활용해서 하나의 변수를 최대값으로 갱신하는 것으로도 결과를 도출할 수 있을 것이라 생각했다.

• 다른 솔루션들도 중복을 제거, 정렬하는 방법으로 접근을 했고, 굳이 dictionary 자료구조를 활용한 솔루션은 거의 없던 것 같다. 현재 코드가 성능도 어느정도 좋게 나왔고, 코드 흐름도 파악하기 쉽다고 생각하여 추가 변경은 하지 않았다.

# Remove Nth Node From End of List

[Quetion]

LeetCode 19. Remove Nth Node From End of List

📌 접근법

[문제 이해]

• 단일 Linked List의 끝에서 n번째 노드를 삭제한 Linked List 반환

끝에서 n번째 노드를 삭제하기 위해서는 마지막 노드를 알아야한다.

문제에서 주어진 Linked List는 데이터와 다음 노드를 가리키는 next 포인터밖에 없는 구조이기 때문에 마지막 노드를 찾기 위해서는 O(n)의 시간복잡도를 가지게 되므로 최대 O(n)을 기준으로 잡고 고민을 해보았다.

다음과 같은 생각의 흐름대로 구현을 시도했다.

• Linked List의 데이터들을 리스트에 담는다
• 끝에서 n번째에 해당하는 데이터를 삭제한다 [O(1)]
• 리스트에 담긴 데이터를 다시 노드로 만든다
• queue 자료구조를 활용하여 노드들을 다시 Linked List가 될 수 있게 연결해준다

💻 구현

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # node 데이터를 담을 list
        dummy = []
        while head:
            dummy.append(head.val)
            head = head.next

        # 끝에서 n번째 데이터 삭제
        dummy.pop(-n)

        # 데이터가 없다면 빈 값을 리턴
        if not dummy:
            return 

        # list 데이터로 노드 생성
        for i in range(len(dummy)):
            dummy[i] = ListNode(dummy[i])

        # 새로운 노드를 만들고, 노드들을 다시 연결
        from collections import deque
        queue = deque(dummy)
        result = queue.popleft()
        curr = result

        while queue:
            node = queue.popleft()
            curr.next = node
            curr = node 
        return result

Runtime: 35ms | Memory: 16.3MB LeetCode 코드 중 Runtime 89%, Memory 64% 해당하는 결과

📌 로직 핵심

• tail이 있는 구조의 Linked List라면 마지막 노드를 찾기 까지 O(1)의 시간복잡도를 가지지만 그렇지 않기 때문에, 끝에서 n번째의 노드를 쉽게 삭제하기 위해 노드의 데이터들을 리스트에 담고 원하는 값을 삭제했다.

• 리스트에 담은 데이터를 다시 Linked List로 만들어 줌.

• 로직의 이해를 돕기 위한 그림은 다음과 같다.

📝 Remove Nth Node From End of List 회고

• 해당 코드의 시간복잡도는 O(N), 공간 복잡도는 O(N)이다.

• 루프를 순회하며 Linked List의 데이터를 담고, 데이터를 다시 Node로 만들면서 O(N)의 시간이 소요된 것이다.

• list에는 Linked List의 순서대로 데이터가 담겨 있기 때문에, 리스트의 앞에서 부터 데이터를 가져와야 했으므로 deque의 popleft 연산을 활용했다. insert(0)도 있지만 insert(0)은 배열의 특성상 O(n)의 시간이 소요되므로 배제했다.

• 다른 솔루션도 확인해보니 포인터 두개를 사용하는 토끼와 거북이 알고리즘을 활용하여 해결한 코드들이 대부분이었다.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        slow, fast = head, head

        while n > 0:
            fast = fast.next
            n -= 1

        while fast and fast.next:
            slow = slow.next
            fast = fast.next

        if fast:
            slow.next = slow.next.next
        else:
            head = head.next
        return head

Runtime: 35ms ---> 35ms Memory: 16.3MB ---> 16.1MB

솔루션을 참고하고, 토끼와 거북이 알고리즘을 활용하여 개선해보았다.

결과적으로 시간복잡도는 같지만 공간복잡도는 O(1)로 개선되었다. 로직의 흐름은 다음과 같다.

빠른 포인터가 마지막 노드에 도착하면 느린 포인터는 끝에서 n번째에 위치하는 것이 핵심이다. 삭제하려는 노드의 이전 노드와 다음노드를 이어줌으로써 삭제가 되는 것이다.

문제를 풀 때는 이런 접근 방법을 생각하지도 못해서 로직을 이해하면서 신기했고, 이런 접근법을 떠올리고자 더 노력해야겠다.

# Container With Most Water

[Quetion]

LeetCode 11. Container With Most Water

📌 접근법

[문제 이해]

• 배열의 길이를 x축, 배열의 값을 기둥의 높이라고 한다.

• 두 기둥 사이에 물을 담을 수 있다고 할 때, 물을 담을 수 있는 최대 용량 구하기

두 기둥을 가리킬 수 있는 포인터 2개가 필요하므로 투 포인터 접근법을 생각했다. 그래서 생각한 코드의 흐름은 다음과 같다.

• 배열의 가장 첫번째 값과 마지막 값을 가리키는 포인터 2개 생성
• 두 포인터가 가리키는 값 중 작은 값을 고른다.
• 물의 양 = 고른 값 * 두 기둥 사이의 거리
• 작은 값을 가진 포인터를 왼쪽 혹은 오른쪽으로 1칸씩 이동

💻 구현

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l,r = 0,len(height)-1
        # 물의 양
        amount = 0
        while l != r:
            # 두 포인터가 가리키는 값 중 더 작은 값
            x = min(height[l], height[r])

            # 계산한 물의 양이 기존 보다 크면 갱신
            amount = max(amount, (x * (r-l)))

            # 더 작은 값을 가리키는 포인터를 이동
            if height[l] <= height[r]:
                l+=1
            else:
                r-=1
        return amount

Runtime: 594ms | Memory: 29.1MB LeetCode 코드 중 Runtime 69%, Memory 96% 해당하는 결과

📌 로직 핵심

• 두 기둥 중 짧은 기둥만큼 물을 채울 수 있으므로 x 변수에 더 짧은 기둥의 높이를 담았다.
• 그리고 x와 두 기둥 사이의 거리인 r-l을 곱하여 물의 양을 구하고, 기존에 계산된 물의 양보다 크면 갱신한다.
• 다음 기둥으로 이동하면서 물을 더 많이 채울 수 도 있기 때문에 더 짧은 기둥을 다른 기둥으로 교체한다.

📝 Container With Most Water 회고

• 해당 코드의 시간복잡도는 O(N), 공간 복잡도는 O(1)이다.

• 코드를 제출하고 다른 대부분의 솔루션들도 max(), min() 함수를 활용하여 투포인터 접근 법으로 문제를 해결한 것을 확인했다.

• abs() 함수로 두 기둥간의 거리를 얻는 코드도 있었다. 똑같은 생각을 했었지만 오른쪽 포인터가 무조건 더 크기때문에 (오른쪽 - 왼쪽)으로 해결할 수 있어서 abs() 활용은 필요하지 않다고 판단했다.

• x변수에 할당한 것을 amount 연산 과정에 합치는 것으로 코드를 더 간결하게 개선할 수 있지만, 코드의 가로 길이가 그만큼 길어지기 때문에 가독성을 낮춘다고 생각하여 따로 개선을 진행하지는 않았다.

2023.08.21 OT를 시작으로 원티드에서 진행하는 프리온보딩 인턴십 - 백엔드 과정이 시작되었다.

처음 확인했던 커리큘럼과는 조금 변경된 점이 있었지만, 오직 알고리즘, 자료구조에 집중하는 방향으로 바뀐 것이라서 오히려 좋았다! 덕분에 자료구조를 공부하는데 큰 도움이 되었다.

매주 2회에 걸쳐 LeetCode에서 알고리즘 문제를 푸는 과제가 있었는데, 처음에는 문제도 영어로 되어있고, 자료구조에도 익숙하지 않아서 많이 어려웠고 상당한 시간이 걸렸다.

하지만 Linked List를 시작으로 Stack, Queue, Tree, BFS, DFS 등 멘토님의 강의를 듣고 스스로 알고리즘을 구현 해보고, 복습하는 과정을 겪으면서 알고리즘 문제를 풀 때 접근하는 방법을 떠올리기가 더 쉬워졌다는 것을 스스로 느꼈다.

혼자서 자료구조, 알고리즘에 대해 공부할 때에는 막막했지만 자료구조를 공부하는 방법에 대해 알 수 있어서 굉장히 유익한 교육이었다고 생각한다. 이외에도 생각나는 것 중 가장 유익하다고 생각한 것은 git 활용법이 있다.

⭐️ 배우게 된 것들

📌 자료구조 & 알고리즘

• Linked List
• Stack, Queue
• HashTable
• Recursion
• Sorting
• Tree ,Trie, Heap, Graph

많아 보이지만 기본적인 자료구조이고, 이렇게 배운 자료구조를 바탕으로 Leetcode 문제들을 풀며 알고리즘을 적용해보았다. 아직 재귀(Recursion)와 Tree 관련 자료구조는 이해는 했지만 코드 구현에 어려움이 있는 것 같아서 더욱 공부 해야겠다고 생각했다.

📌 Git 활용

자료구조 & 알고리즘 이외에도 팀 과제, 팀 프로젝트를 진행했다.

학교를 졸업하고 혼자 개발하는 시간이 길어져서 함께 개발을 진행해 볼 기회가 잘 없었는데, 팀 과제를 계기로 팀 프로젝트도 진행하며 협업시 git 활용이 얼마나 중요한 일인지 배우게 되었다.

• 혼자 개발 할 때에는 아래 명령어만을 대충 활용했던 것 같다.

  git add . 
  git commit -m""
  git push origin branch

• 하지만 Readme.md의 중요성, git commit & PR message의 중요성을 알게 되었고, 현재는 더 꼼꼼히 사용할 수 있도록 습관화를 하고 있다.

  git status 
  git diff
  git commit "[type] title  body  footer"

• git status : 명령어로 commit 전 파일들을 확인하고 불 필요한 파일들이 포함되지 않도록 주의 한다.

• git diff : 명령어로 commit 전 수정 내용이 정확한지 다시 한번 확인한다.

• git commit : commit별 타입을 구분하고, 1 commit에 1개의 내용만 포함되도록 commit을 세분화하고 body를 활용하여 상세하게 기입한다.

• PR (Pull request) : commit처럼 title에 타입을 작성해주고, 무엇을, 어떻게, 왜, 테스트 결과, 중요하게 볼 부분 처럼 상세한 내용들을 PR 메시지에 녹여내서 팀원들이 코드리뷰를 하기 쉽도록 작성해준다.

현재 팀 프로젝트인 실시간 경매 서비스 (github)에서는 개발도 중요하지만 이러한 git commit, PR을 신경 쓰며 진행하고 있고, 팀원들끼리 코드리뷰도 진행하고 있다. 이후 어느정도 개발이 진행되었을 때 Readme 파일도 상세히 정리할 예정이다.

자료구조, 알고리즘도 매우 중요하고 유익했지만! git 활용법 또한 실무에서 굉장히 유용하게 사용할 것 같아서 큰 도움이 되었고, 여태까지 혼자 개발할 때는 크게 신경쓰지 않았지만 이제 부터라도 모든 git 활용을 꼼꼼히 할 수 있도록 꾸준히 규칙들을 지켜나가야겠다고 생각했다.

[참고] 이 링크는 현재 진행하는 팀 프로젝트에서 실제로 직접 PR을 한 내용이다. 실시간 경매 서비스 PR

매일 과제, 강의, 공부를 하며 1달이 정말 빠르게 지나갔고, 프리온보딩 인턴십 과정은 어제로 끝이 났다.

그래도 팀원들과의 팀 프로젝트는 꾸준히 이어갈 예정이고 탄탄한 프로젝트로 완성하고 싶다, 알고리즘 역시 배운 자료구조를 바탕으로 꾸준히 풀고 공부해봐야겠다!

그리고 아직 2주 간의 취업 집중 과정도 남아 있기에 늘어지지 않고 열심히 달려야겠다 :D

실시간 경매 서비스 팀 프로젝트를 진행 중 merge 과정에서 오류가 발생했다!

• 이후에도 같은 상황이 발생했을 때 대처를 잘 하기 위해
• 같은 상황의 오류를 맞이하신 분들을 위해 이 글을 남깁니다.

🚨 문제 상황

• 각자의 역할을 Django app을 기준으로 나눈 상황
• 각자 DB Model을 작성하여 develop branch에 merge
• repo 책임자가 develop branch에 DB migrations을 진행하여 올림
• 팀원 분 중 한분이 pull을 진행하지 않고, DB Model을 수정 하고 migrations 후 PR

결국 이미 migrations을 진행한 develop branch의 migration 폴더와 PR 요청을 하신 팀원의 migration 폴더 내부의 파일과 충돌 발생

⭐️ 원인

migration이 가장 처음 진행되면 0001_intial.py가 생성되는데, 협업시 이를 pull 받지 않고 다시 migration을 진행하면 0002_intial.py 파일이 생성되는게 아니라 0001_intial.py이 생성되고 merge 과정에서 충돌이 발생하는 것

💡 해결

• 로컬에서 migration한 파일들을 지우고, develop branch를 다시 pull을 받은 후 merge

하지만 3명 이상이 git을 통해 협업을 하는 과정에서 다시 DB migration 충돌 문제가 발생할 것을 우려했다. 그래서 다음과 같은 방법을 사용하여 해결했다.

• .gitignore 파일에 migration 폴더 자체를 추가

이렇게 하면 git에 올라가지 않게 관리하여 충돌 문제를 해결 할 수 있다. 단, 배포 과정에서는 다시 git에 올라가도록 조치를 취해야하며, 개발 과정에서만 충돌 문제를 해결하기 위함이다.

또한 이 방법은 DB 관련 코드에 변경사항이 발생했을 때, pull을 받고 개인이 migration을 진행해야 한다는 번거로움이 있다.

✋🏻 [추가적인 고려사항]

이렇게 .gitignore 파일에 항목을 추가했을 때 적용이 안되는 문제가 있는데, 이는 git에 .gitignore 항목들이 캐시되어서 발생하는 문제이다.

git rm -r --cached

따라서 위 명령어를 적용한 후 git add ., git push ~ 를 진행하면 문제없이 .gitignore가 작동한다.

회고

혼자 프로젝트를 진행했을 때 보다 팀 프로젝트시 경험하는 범위가 더 크기 때문에, 에러사항이나 문제상황이 발생했을 때 배우거나, 다양한 문제를 대처할 수 있어서 오히려 더 좋은 것 같다.

merge 과정은 어떤 새로운 문제가 발생할 지 모르기에 항상 긴장이 되는 것 같다 :D

# Clone Graph

[Quetion]

LeetCode 133. Clone Graph

📌 접근법

[문제 이해]

Node로 구성된 Graph를 그대로 반환

말 그대로 그래프를 복사하여 새로 반환하는 문제이다.

그러기 위해서는 노드를 탐색해야 했고, 순회 알고리즘 중 BFS 방법을 사용했다. 코드의 흐름은 다음 그림 같이 구성했다.

💻 구현

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        from collections import deque

        if node is None:
            return None

        visited = {}
        queue = deque([node])
        visited[node] = Node(node.val)

        while queue:
            curr = queue.popleft()
            for i in curr.neighbors:
                if i not in visited:
                    queue.appendleft(i)
                    visited[i] = Node(i.val)
                visited[curr].neighbors.append(visited[i])
        return visited[node]

Runtime: 40ms | Memory: 16.65MB LeetCode 코드 중 Runtime 85%, Memory 89% 해당하는 결과

queue에 값이 존재한다면 queue에서 pop한 값을 현재 노드로 지정하고, 현재 노드의 인접한 값으로 반복하는데 visited에 인접 값이 없다면 queue에 push하고 visited에도 값을 키로 하여 노드를 저장한다.

그리고 visited에서 현재 노드를 키 값으로 하는 인접 값의 리스트에 방문한 노드를 추가하고 이를 queue가 빌 때 까지 반복하게 된다.

📝 Clone Graph 회고

• deque() 모듈을 활용하여 queue를 사용했고, 탐색한 노드를 저장하기 위해 visited라는 해쉬테이블을 활용했다.

• 시간복잡도는 정점의 개수인 V, 간선의 개수 E라 했을 때, O(V + E)를 가진다.

• 다른 솔루션에서도 같은 방법으로 많이 푼 것 같고, 현재 더 이상 개선할 것은 없다고 생각된다.

• 한 가지 간과했던 점은 node가 없을 경우 None을 return해줘야 visited[node] 부분에서 오류가 발생하지 않을거라는 점이다. 그 점을 빼먹고 다시 한번 고민해보다가 실수한 것을 깨닫게 되었다.

# Is Subsequence

[Quetion]

LeetCode 392. Is Subsequence

📌 접근법

[문제 이해]

• t 문자열에서 특정 문자를 제거한 하위 문자열 s가 맞으면 True

처음에는 s문자열이 단순히 t문자열에 있으면 True가 된다고 판단하여 코드를 구현했다.

# 실패한 시도
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # t 안에 s가 있는지 확인
        for i in s:
            if i not in t:
                return False
        return True 

하지만 단순히 있는지 확인하는 것이 아니라 s문자열의 순서에 맞게 t문자열에 포함되어야 했다. 그래서 실패한 시도에 더하여 s문자열이 t문자열에 있으면 t에서 그 문자열의 인덱스까지 슬라이싱하는 방법으로 접근했다.

💻 구현

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        for i in s:
            if i not in t:
                return False
            if i in t:
                t = t[t.index(i)+1:]
        return True

Runtime: 42ms | Memory: 16.3MB LeetCode 코드 중 Runtime 53%, Memory 88% 해당하는 결과

📝 Is Subsequence 회고

• 구현한 코드의 시간 복잡도는 O(s * t)이므로 O(n)의 시간복잡도 보다 느리다.

• in 연산자도 O(n)의 시간복잡도를 가지고, index() 함수도 O(n)의 시간복잡도가 걸리기 때문이다.

• 그래서 포인터를 for문 내부의 포인터와 s를 가르키는 포인터 2개를 활용하는 투포인터 접근법으로 다시 개선했다.

  class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        pointer = 0
        if len(s) == 0:
            return True
  
        for i in t:
            if len(s) <= pointer:
                break
            if s[pointer] == i:
                pointer += 1
  
        if len(s) == pointer:
            return True
        else:
            return False

• Runtime*: 42ms ---> 28ms

• Memory*: 16.3MB ---> 16.4MB

• 가장 처음 s가 ""일 경우, 모든 t에 포함되므로 True 반환

• s의 길이보다 포인터의 길이가 크면 반복문을 탈출 (index out of error 방지)

• 포인터가 가르키는 s문자열이 t문자열과 같으면 포인터가 s의 다음 문자열을 가르킴

• 만약 포인터의 길이와 s 문자열의 길이가 같다면 모두 포함된다는 의미라서 True

코드는 조금 더 복잡해졌지만, 투포인터 접근법을 활용하여 시간복잡도는 O(t)즉 O(n)으로 개선되었다. 그래서 leetcode 기준 98%의 Runtime으로 속도를 2배가량 개선하게 되었다.