Jun's TID

사실, 한참 전에 풀이를 시작했는데, 연결리스트의 조회나, 삭제와 같은 기능의 구조를 이해하고 구현해서 문제에 적용시키는데 굉장히 오랜 시간이 걸렸다. 자바의 경우 Util 패키지에서 해당 자료 구조의 객체를 지원하지만, 파이썬은(아마 내 생각엔) 리스트가 어느 정도 연결리스트의 역할을 하기 때문에 굳이 내장 객체를 지원하지 않는 것 같다. 바로 풀이를 보자. class ListNode: def __init__(self, data): self.val = data self.next = None class LinkedList: def __init__(self): head_node = ListNode(None) self.head = head_node self.tail = head_node self.num_of..

간단하게 구현한 단방향 연결 리스트이다. 이렇게 아예 구현해놓고 문제를 푸는 게 삽입, 삭제, 조회 등을 추가하여 사용하기가 훨씬 편리할 거 같아서 작성했다. class ListNode: def __init__(self, data): self.val = data self.next = None class LinkedList: def __init__(self): head_node = ListNode(None) self.head = head_node self.tail = head_node self.num_of_data = 0 def insert(self, data): insert_node = ListNode(data) self.tail.next = insert_node self.tail = insert_nod..

앞서도 몇번 언급했듯이, ArrayList와 같은 연결 리스트는 자료들이 노드로 하나씩 연결되어 있는 형태이기 때문에, 자료의 삽입이나 삭제는 O(1) 의 매우 유리한 시간 복잡도를 가지지만, 탐색은 노드를 따로 불러올 수 없고, 리스트 전체를 훓어가면서 찾아야 하기 때문에 최악의 경우 O(n)의 복잡도를 가진다. 그렇기 때문에 연결 리스트를 탐색, 비교하는 문제를 풀 때, 문제가 조금 복잡해지면 빈번하게 타임 아웃이 일어나기 쉽다. 이번 포스팅에서는 이런 연결 리스트의 탐색 속도를 2개의 포인터를 이용하여 조금이나마 향상시킬 수 있는 방법인 Runner 기법에 대하여 다룰 것이다. 1. Runner? Runner 기법은 연결 리스트를 순회할 때, 2개의 포인터를 동시에 사용하는 기법이다. 한 포인터가 ..

제약 조건이 없다면 미리 값들을 모두 곱한 다음에 이터레이터가 되는 값을 나눠서 간단하게 구할 수 있지만... 제약조건이 있기 때문에 시간 복잡도를 맞추기 위해서는 이터레이터가 되는 값의 왼쪽을 모두 곱한 결과에 오른쪽 값을 모두 곱한 값을 곱해줘서 구해볼 수 있다. (이것도 한참 고민하다가 모범 답안을 본 건데, 진짜 미친 풀이인 거 같다...) from typing import List def multiply(nums_list: List[int]) -> List[int]: result = [] left_p = 1 right_p = 1 # 이터레이터 기준 왼쪽 값들의 곱을 저장 for i in range(0, len(nums_list)): result.append(left_p) left_p *= num..

포인터를 정해놓고 리스트 인덱스를 옮겨가며, 연산 후 비교하는 로직을 구성하면 쉽게 풀 수 있으나, 문제는 세 수의 합이기 때문에 자칫 삼중 for문을 사용하는 불상사가 발생할 수 도 있다. 이 문제 역시 두 개의 포인터를 사용하여 쉽게 풀이가 가능하다. 1 씩 증가하는 리스트 인덱스 i를 만들어 놓은 뒤, i 뒤쪽의 나머지 배열의 양 끝을 left와 right로 나눈다. 이때, i, left, right 위치의 값들을 더하여 0과 비교하고, 0보다 작다면 right를 감소, 크다면 left를 증가시키는 방식으로 풀이할 수 있다. from typing import List def sum_of_three(nums_list: List[int]) -> List[List[int]]: nums_list.sort(..

리스트를 사용하는 조금 난이도 있는 문제를 가지고 왔다. 벽들의 높이를 리스트로 입력받아, 빗물이 쌓일 수 있는 면적을 구하는 문제이다. 처음에는 한개의 포인터로, 더 높은 벽을 만날 때마다 포인터를 높은 벽의 높이로 갱신하며, 이전 포인터 까지의 격차를 더하여 푸려고 계획했다. 그러나, 포인터를 한개만 사용하면, 가장 높은 벽(예시에서는 3)을 만난 뒤에는 포인터를 갱신할 수 없는 문제가 발생하고, 이 문제를 해결하려면 꽤나 복잡한 로직이 동반된다. 그래서, 가장 높은 벽을 기준으로 양 끝, 두개의 포인터를 이용하여 풀이를 작성했다. 1. 두개의 포인터를 이용하여 풀이 from typing import List def trap(rain: List[int]) -> int: sum = 0 left = 0 ..

선형 자료구조를 다루는 가장 기초적인 문제로, 리트 코드의 1번 문제라서 한번 가져와 봤다. 문제는 단순 비교하여 값을 리턴한다고 구성하면 아마 초등학생도 풀 수 있는 정도의 난이도의 문제이지만, 의외로 최적화할 수 있는 방법이 많아서 다뤄보려고 한다. 1. 무차별 대입 방식 from typing import List def twoSum(nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i, j] if __name__ == '__main__': nums = [2, 5, 7, 9] target = 9 p..