반응형
LEETCODE의 Top Interview Questions의 Easy Collection을 풀어보았습니다.
전체 문제를 다 풀지는 않았고 각 챕터별로 recommended 라고 나와 있는 문제만 풀었습니다.
(string이랑 array는 문제가 어렵지 않아 대부분 skip했습니다.)
쉬운 문제도 많았지만, 코테에 나오는 주요 유형들을 되짚어보기 위해 가벼운 마음으로 풀어보기에는 적합했던 것 같습니다.
코테 준비를 오랜만에 하신다면 본격 Medium, Hard 풀기 전에 한 번 훑어보시기를 추천드립니다.
https://leetcode.com/explore/interview/card/top-interview-questions-easy/
Explore - LeetCode
LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore.
leetcode.com
일주일에 거쳐 총 21문제를 풀었네요.
모든 문제에 대한 python3 풀이와 해설을 공유하겠습니다.
01. 727 | ARRAY | Single Number
https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/727/
정렬된 리스트에서 unique 값의 갯수를 반환하는 문제입니다.
정렬된 리스트이므로, 리스트의 바로 전 값과만 비교하면 중복값인지 알 수 있습니다.
이전값과 같으면 현재 인덱스를 삭제합니다.
from typing import List
class Solution(object):
def removeDuplicates(self, nums: List[int]) -> int:
def helper(nums, currIndex):
# print(nums, currIndex)
if currIndex == len(nums):
return currIndex
if nums[currIndex] == nums[currIndex-1]:
del nums[currIndex]
return helper(nums, currIndex)
else:
return helper(nums, currIndex+1)
return helper(nums, 1)
nums = [1,1,2]
nums = [0,0,1,1,1,2,2,3,3,4]
nums = [1, 2, 3]
nums = [-50,-50,-49,-48,-47,-47,-47,-46,-45,-43,-42,-41,-40,-40,-40,-40,-40,-40,-39,-38,-38,-38,-38,-37,-36,-35,-34,-34,-34,-33,-32,-31,-30,-28,-27,-26,-26,-26,-25,-25,-24,-24,-24,-22,-22,-21,-21,-21,-21,-21,-20,-19,-18,-18,-18,-17,-17,-17,-17,-17,-16,-16,-15,-14,-14,-14,-13,-13,-12,-12,-10,-10,-9,-8,-8,-7,-7,-6,-5,-4,-4,-4,-3,-1,1,2,2,3,4,5,6,6,7,8,8,9,9,10,10,10,11,11,12,12,13,13,13,14,14,14,15,16,17,17,18,20,21,22,22,22,23,23,25,26,28,29,29,29,30,31,31,32,33,34,34,34,36,36,37,37,38,38,38,39,40,40,40,41,42,42,43,43,44,44,45,45,45,46,47,47,47,47,48,49,49,49,50]
sol = Solution()
print(sol.removeDuplicates(nums))
02. 646 | ARRAY | Rotate Array
https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/646/
input list의 마지막 k개 요소를 list 맨 앞으로 넣어 반환하는 문제입니다.
from typing import List
class Solution(object):
def rotate(self, nums: List[int], k: int) -> None:
for i in range(k):
# print(i)
lastElement = nums.pop()
nums.insert(0, lastElement)
# print(nums)
nums = [1,2,3,4,5,6,7]
k = 3
sol = Solution()
print(sol.rotate(nums,k))
03. 879 | STRING | Reverse String
https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/879/
문자열을 in-place(별도 메모리 소모 없이) 뒤집는 문제입니다.
파이썬이라서 코드가 간단하네요 ㅎㅎ
swap할 때 그냥 a,b = b,a 하면 끝
from typing import List
class Solution(object):
def reverseString(self, s: List[str]) -> None:
lenStr = len(s)
for i in range(lenStr//2):
# print(i)
s[i], s[lenStr-1-i] = s[lenStr-1-i], s[i]
# print(s)
s = ["H","a","n","n","a","h"]
sol = Solution()
print(sol.reverseString(s))
04. 560 | LINKED LIST | Reverse Linked List
https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/560/
링크드리스트를 많이 안써봐서;; 좀 헤맸던 문제였습니다.
처음에는 bubble sort하듯이 2개씩 다 swap해서 순서를 바꿔야 하는줄 알았는데
그냥 화살표 방향만 바꾸면 되는거였어요.
이 문제는 못풀어서 결국 discussion의 다른 답안을 참고해서 풀었습니다 (ㅠㅠ)
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def printNode(self, head):
print(head.val)
if(head.next):
self.printNode(head.next)
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev_node, curr_node = None, head
while curr_node:
temp_next = curr_node.next
curr_node.next = prev_node
prev_node = curr_node
curr_node = temp_next
return prev_node
input = [1,2,3,4,5]
if len(input) > 0:
head = ListNode(input[0])
targetNode = head
for i in range(1, len(input)):
targetNode.next = ListNode(input[i])
targetNode = targetNode.next
sol = Solution()
sol.printNode(head)
head = sol.reverseList(head)
sol.printNode(head)05. 771 | LINKED LIST | Merge Two Sorted List
https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/771/
input으로들어온 두 리스트에 대한 pointer를 두고
둘 중 작은 수 먼저 새로운 list에 넣습니다.
# Definition for singly-linked list.
# 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]:
if list1 is None:
return list2
if list2 is None:
return list1
if list1.val < list2.val:
return ListNode(list1.val, self.mergeTwoLists(list1.next, list2))
else:
return ListNode(list2.val, self.mergeTwoLists(list2.next, list1))06. 772 | LINKED LIST | Palindrome Linked List
https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/772/
중간 아이템을 기준으로 왼쪽은 list를 reverse하여 두 list가 같으면 Paindrome이 됩니다.
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def printNode(self, head):
if head is None:
return print()
print(head.val)
self.printNode(head.next)
def isPalindromeTwoPointer(self, head_1: Optional[ListNode], head_2: Optional[ListNode]):
if head_1 and head_2 and head_1.val is head_2.val:
if head_1.next is None and head_2.next is None:
return True
return self.isPalindromeTwoPointer(head_1.next, head_2.next)
return False
def isPalindrome(self, head: Optional[ListNode]) -> bool:
# if list contains only one item => always true
if head.next is None:
return True
## keep the list in two direction and remember head of each list
### O <- O <- O O -> O -> O ..
### p c
prev_node, curr_node = None, head
while curr_node:
# 1) Even Palindrome : the two list looks exactly the same
# ex) 1 <- 2 <- 3(p) 3(c) -> 2 -> 1
if self.isPalindromeTwoPointer(prev_node, curr_node):
return True
# 1) Odd Palindrome : prev_node list and the list after curr_node looks exactly the same
# ex) 1 <- 2(p) 3(c) -> 2 -> 1
if self.isPalindromeTwoPointer(prev_node, curr_node.next):
return True
# current node is not the middle point of the Palindrome
# swap curr_node's pointer direction
# ex) 1(p) 2(c) -> 3 -> 2 -> 1
# => 1 <- 2(p) 3(c) -> 2 -> 1
temp_next = curr_node.next
curr_node.next = prev_node
prev_node = curr_node
curr_node = temp_next
return False
input = [1,2,3,4,5]
input = [1,2,3,2,1]
input = [1,2,3,2,2,3,2,1]
# input = [1,2,3,32,2,3,2,1]
input = [0,0]
if len(input) > 0:
head = ListNode(input[0])
targetNode = head
for i in range(1, len(input)):
targetNode.next = ListNode(input[i])
targetNode = targetNode.next
sol = Solution()
result = sol.isPalindrome(head)
print(result)
07. 555 | TREE | Maximum Depth of Binary Tree
https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/555/
코드가 긴데.. Solution 의 maxDepth부분만 보면 됩니다.
나머지는 그냥 개발용.. 트리 만들고 프린트하는 부분
recursive하게 왼쪽과 오른쪽 subtree의 maxDepth를 확인합니다.
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root: return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
def setTree(list):
if len(list) is 0:
return None
headNode = node = TreeNode(list.pop(0))
leafNodeList = [headNode]
while len(list) > 0:
targetNode = leafNodeList.pop(0)
targetNode.left = TreeNode(list.pop(0))
leafNodeList.append(targetNode.left)
if len(list) > 0:
targetNode.right = TreeNode(list.pop(0))
leafNodeList.append(targetNode.right)
return headNode
def printTree(head):
if head is None:
return
if head.left:
print(head.left.val)
if head.right:
print(head.right.val)
printTree(head.left)
printTree(head.right)
root = [3,9,20,None,None,15,7]
head = setTree(root)
print(head.val)
printTree(head)
sol = Solution().isValidBST(head)
print(sol)
08. 555 | TREE | Validate Binary Search Tree
https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/625/
유효한 binary tree가 맞는지 확인하는 문제입니다.
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValidNode(node, min, max):
if not node: return True
if node.val <= min or node.val >= max: return False
return isValidNode(node.left, min, node.val) and isValidNode(node.right, node.val, max)
return isValidNode(root, float("-inf"), float("inf"))
root = [5,4,6,None,None,3,7]
def setTree(list):
if len(list) is 0:
return None
headNode = node = TreeNode(list.pop(0))
leafNodeList = [headNode]
while len(list) > 0:
targetNode = leafNodeList.pop(0)
item = list.pop(0)
if item:
targetNode.left = TreeNode(item)
leafNodeList.append(targetNode.left)
if len(list) > 0:
item = list.pop(0)
if item:
targetNode.right = TreeNode(item)
leafNodeList.append(targetNode.right)
return headNode
def printTree(head):
if head is None:
return
if head.left:
print(head.left.val)
if head.right:
print(head.right.val)
printTree(head.left)
printTree(head.right)
head = setTree(root)
# print(head.val)
# printTree(head)
sol = Solution().isValidBST(head)
print(sol)
09. 628 | TREE | Binary Tree Level Order Traversal
https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/628/
tree를 순회하며 층별로 출력하는 문제입니다.
왼쪽, 오른쪽 노드를 출력 후 각각의 subtree도 출력하기 위해 stack에 넣습니다.
stack에 있는 아이템을 꺼내며 출력하면 층별로 출력이 됩니다. (층별로 stack에 들어가므로..)
from typing import Optional, List
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
list = []
def traverse(root, level):
if not root:
return
if len(list) <= level:
list.append([])
list[level].append(root.val)
traverse(root.left, level+1)
traverse(root.right, level+1)
traverse(root, 0)
return list
root = [3,9,20,None,None,15,7]
root = [1]
def setTree(list):
if len(list) is 0:
return None
headNode = node = TreeNode(list.pop(0))
leafNodeList = [headNode]
while len(list) > 0:
targetNode = leafNodeList.pop(0)
item = list.pop(0)
if item:
targetNode.left = TreeNode(item)
leafNodeList.append(targetNode.left)
if len(list) > 0:
item = list.pop(0)
if item:
targetNode.right = TreeNode(item)
leafNodeList.append(targetNode.right)
return headNode
def printTree(head):
if head is None:
return
if head.left:
print(head.left.val)
if head.right:
print(head.right.val)
printTree(head.left)
printTree(head.right)
head = setTree(root)
# print(head.val)
# printTree(head)
sol = Solution().levelOrder(head)
print(sol)
10. 631 | TREE | Convert Sorted Array to Binary Search Tree
https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/631/
처음에 array가 sorted가 아닌 상태로 bst 만들어야 하는줄 알고 헤맸네요..;;
sorted array가 들어오므로 가운데 값을 head노드로 해서
왼쪽, 오른쪽 subarray로 subtree를 만들면 됩니다.
list slicing을 해서 넘기면 오래걸리므로 left, right index만 같이 넘겨주는게 좋습니다.
from typing import Optional, List
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def dfs(st, ed):
if st > ed: return
mid = (st + ed)//2
root = TreeNode(nums[mid])
root.left = dfs(st, mid-1)
root.right = dfs(mid+1, ed)
return root
return dfs(0, len(nums)-1)
root = [3,9,20,None,None,15,7]
root = [1]
def setTree(list):
if len(list) is 0:
return None
headNode = node = TreeNode(list.pop(0))
leafNodeList = [headNode]
while len(list) > 0:
targetNode = leafNodeList.pop(0)
item = list.pop(0)
if item:
targetNode.left = TreeNode(item)
leafNodeList.append(targetNode.left)
if len(list) > 0:
item = list.pop(0)
if item:
targetNode.right = TreeNode(item)
leafNodeList.append(targetNode.right)
return headNode
def printTree(head):
if head is None:
return
if head.left:
print(head.left.val)
if head.right:
print(head.right.val)
printTree(head.left)
printTree(head.right)
# head = setTree(root)
# print(head.val)
nums = [-10,-3,0,5,9]
sol = Solution().sortedArrayToBST(nums)
printTree(sol)반응형
'알고리즘 > LEETCODE' 카테고리의 다른 글
| Group Anagrams | LeetCode 778 | Python3 🐍 (0) | 2022.02.27 |
|---|---|
| [LEETCODE] Python3 🐍 | Easy Collections 추천문제 및 풀이 (2) Sorting&Searching, Dynamic Programming, Design, Math, Others (0) | 2022.02.23 |
| Longest Substring Without Repeating Characters | LeetCode 779 | Python3 🐍 (0) | 2022.02.22 |
| Longest Valid Parentheses | LeetCode 32 (0) | 2021.08.03 |
| Maximum Frequency Stack | LeetCode 895 (0) | 2021.08.01 |
