[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파
START :
[3코1파] 2023.01.04~ (299일차)
[4코1파] 2023.01.13~ (291일차)
[4코3파] 2023.10.01 ~ (29일차)
Today :
2023.10.29 [299일차]
Leetcode Linked List
[1] 206. Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/description/
문제 설명
단일 연결 리스트의 head가 주어질 때, 해당 리스트의 원소를 반전해 리스트로 반환한다.
문제 풀이 방법
링크드 리스트는 인덱스로 접근하는 것이 아니라, 순차적으로 next 메소드를 통해서 옆 원소로 이동할 수 있다. 반전된 원소를 가져오기 위해서 pointer를 2개 두고, 현재 위치와(cur), 현재의 이전 위치 (prev)를 update 해온다.
예를 들어 1->2->3->4로 구성되어 있는 연결형리스트가 주어진다면,
현재의 위치는 1, 이전의 위치는 None으로 초기화한다.
연결형 리스트를 순차적으로 탐색해 나가는데, 현재의 위치는 기존의 이전의 위치 None이 되고 이전의 위치는 1이 된다. 이렇게 이전과 현재의 위치를 이동시켜나가면서 업데이트 해가면서 reverse 된 원소를 update 해 나간다.
내 코드
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
#recursive
if not head:
return None
newHead = head
if head.next:
newHead = self.reverseList(head.next)
head.next.next = head
head.next = None
return newHead
[2] 21. Merge Two Sorted Lists
문제 설명
오름차순으로 구성된 두 개의 링크드리스트가 있을 때, 두 링크드 리스트를 merge 한 후 정렬된 원소로 구성된 링크드 리스트를 반환한다.
문제 풀이 방법
먼저 비워져 있는, dummy linked list를 생성한다.
두 개의 linked list의 현재의 val을 비교해서, 상대적으로 더 낮은 링크드리스트를 dummy linked list의 next에 넣으면서, 이를 업데이트 해가면서 dummy linked list를 오름차순으로 채운다.
그 이후 dummy linksed list의 값을 반환한다.
여기서 주요한 점은 비워져 있는 linked list는 처음의 val은 0 next 부터가 비워져 있는 linked list로 생성한다는 것이고,
더 낮은 링크드리스트 현재의 값을 가진 list1, list2는 다음 노드가 헤드가 되도록 계속 next를 통해서 업데이트 해줘야 하는 것
마지막 dummy변수는 next 에 넣기 시작했으므로 next를 return 하는 것이다
내 코드
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
node = dummy
while list1 and list2:
if list1.val <= list2.val:
node.next = list1
node = node.next
list1 = list1.next
else:
node.next = list2
node = node.next
list2 = list2.next
if list1:
node.next = list1
else:
node.next = list2
return dummy.next
[3] 143. Reorder List
문제 설명
문제 풀이 방법
단일 연결 리스트가 주어질 때,
L0 → L1 → … → Ln - 1 → Ln
다음 형식이 되도록 목록을 재정렬하여 리턴한다.
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
목록 노드의 값은 수정할 수 없고 노드 자체만 변경하여야 한다.
내 코드
너무 복잡하고요..
반갈 해서 그걸 위에서 풀었던 reverse 하는 로직까지 들어가고요..
이것도 이해가 잘 안되서 다시 풀어봐야 할 것 같음
[4] 19. Remove Nth Node From End of List
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
문제 설명
연결형 리스트가 주어졌을 때, 끝에서 n번째 노드를 제거한 후의 연결형 리스트를 반환함
문제 풀이 방법
two pointer가 필요한데, 첫 번째 head에서 시작하는 포인터 하나(left)
그리고 첫번째 포인터에서 +n번째 위치에 있는 포인터 하나(right)를 두고 시작한다.
연결형 리스트는 인덱스로 접근을 하지 못하기 때문에
dummy linked list를 하나 만들어 놓고 해당 링크드 리스트를 가지고 탐색한다.
n만큼 right를 움직이고,
해당 right가 마지막 노드 None 값까지 이동하는 위치만큼 left 도 움직여준다.
해당 left의 next가 마지막에서 n번째 노드로
left.next의 노드를 그다음의 다음의 노드로 바꿔주고 dummy의 next를 return 한다.
내 코드
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
left = dummy
right = head
while n>0 and right:
right = right.next
n -= 1
while right:
left = left.next
right = right.next
left.next= left.next.next
return dummy.next
[5] 138. Copy List with Random Pointer
https://leetcode.com/problems/copy-list-with-random-pointer/
문제 설명
문제 풀이 방법
이거 사실 이해가 잘 안가지 말입니다?
일단 해쉬맵을 사용해서 주어진 node들의 값을 저장하고
해쉬맵에서 불러오는 것 같은데.. 링크드 리스트.. 너란녀석 어렵다
내 코드
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head: Node) -> Node:
oldToCopy = {None : None}
cur = head
while cur:
copy = Node(cur.val)
oldToCopy[cur] = copy
cur = cur.next
cur = head
while cur:
copy = oldToCopy[cur]
copy.next = oldToCopy[cur.next]
copy.random = oldToCopy[cur.random]
cur = cur.next
return oldToCopy[head]
[6] 2. Add Two Numbers
문제 설명
linked list가 2개 주어질 때, 각 linked list의 reverse된 원소들의 합을 linked list 형태로 return 함
문제 풀이 방법
주어진 링크드 리스트를 처음부터 탐색하면서 값을 더해가는데,
각 자리씩 더해가는 와중에 10이 넘어가면 다음 노드에 그만큼의 합을 넘겨줘야 하므로 carry 라는 변수에 더한 값의 몫을 넘겨준다.
주어진 두개의 링크드 리스트의 길이가 같지 않을 경우도 생기므로, 해당 조건에 맞춰서 링크드 리스트를 업데이트 시켜줘야 한다.
내 코드
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
val = v1+v2+carry
carry = val//10
val = val%10
cur.next = ListNode(val)
cur = cur.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
[7] 141. Linked List Cycle
https://leetcode.com/problems/linked-list-cycle/description/
문제 설명
링크드 리스트의 헤드가 주어 질때, 해당 링크드 리스크가 순환하는 링크드 리스트라면 True, 아니라면 False를 반환한다.
링크드 리스트와 함께 pos라는 인덱스가 주어지는데, 노드의 가장 마지막 포인터가 연결된 노드의 인덱스를 나타낸다.
문제 풀이 방법
순환하는 모양이라면, 어디에서부터 출발 했던지 어느 한지점에서 만나게 되어 있다. 그래서 한번에 한 칸 이동하는 slow 포인터와 한 번에 두칸 씩 이동하는 fast 포인터를 둬서,
fast 포인터와 fast의 다음 포인터가 끝 경로 까지 가는 동안 루프를 돌린다. 해당 루프 안에서 slow 지점과 만난다면 순환하므로 True, 끝나도록 만나지 못한다면 순환하지 않는 걸로 판단해서 False를 return 한다.
내 코드
시간복잡도 O(n), 공간복잡도 O(1) 로 풀 수 있다.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow==fast:
return True
return False
[8] 287. Find the Duplicate Number
문제 설명
n + 1개의 정수를 포함하는 정수 배열 nums가 주어지며, 각 정수는 [1, n] 범위에 속한다.
nums에는 반복되는 숫자가 하나만 존재할 때, 반복되는 숫자를 반환한다.
배열 번호를 수정하지 않고 문제를 해결해야 하고, 일정한 추가 공간만 사용가능하다.
문제 풀이 방법
플루이드 정렬을 사용하면 된다는데...
일단.. 알고리즘 코드는 이해했는데
p..어쩌고 s 어쩌고가.. 모르겠다 다시 가보자고
내 코드
class Solution:
def findDuplicate(self, nums: list[int]) -> int:
slow, fast = 0,0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow==fast:
break
slow2=0
while True:
slow = nums[slow]
slow2 = nums[slow2]
if slow == slow2:
return slow
여담
나머지 LRU cache랑 hard 문제는 대갈아파서 1시간 쉬다가 해야지
