0001. Two Sum / 0268. Missing Number
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dct = dict()
for i in range(len(nums)):
dct[nums[i]] = i
for i in range(len(nums)):
if (target-nums[i]) in dct:
if i!=dct[target-nums[i]]:
return [i,dct[target-nums[i]]]
class Solution:
def missingNumber(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums)):
if i==0:
if nums[i] != 0:
return 0
else:
if nums[i] != (nums[i-1]+1):
return (nums[i-1]+1)
return len(nums)
๐งก 0001) [2, 7, 11, 15]๋ฅผ list๋ก ๋๋ฆด ๋ target์ด 9์ผ ๊ฒฝ์ฐ 2 ๋ ์์ ์ ์ ์ธํ 7์ด list์ ์กด์ฌํ๋ ์ง๋ฅผ hash map O(1)๋ก ๊ตฌํํด ์๋์ ์ผ๋ก ๋น ๋ฅธ ์๊ฐ ๋ด์ ์ ๋ต ์ฝ๋ ๊ตฌํ ๊ฐ๋ฅ
๐งก 0268) ๋จผ์ sort()๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌํ ๋ค, ๋งจ ์์ด 0์ด ์๋๋ฉด ๋ฐ๋ก 0 ์ถ๋ ฅ. index 1 ์ด์์ผ ๊ฒฝ์ฐ ๋ฐ๋ก ์์ index์์ ์ฐจ์ด๊ฐ 1์ด ์๋๋ฉด ๋ฐ๋ก ์์ index + 1์ ์ถ๋ ฅ. ๋งจ ๋ง์ง๋ง๊น์ง ๋ชจ๋ ์ ์์ ์ผ๋ก +1์ด ๋ค ๋์๋ค๋ฉด ๋งจ ๋ง์ง๋ง ์ซ์ ์ถ๋ ฅ
0020. Valid Parentheses / 0232. Implement Queue Using Stacks
class Solution:
def isValid(self, s: str) -> bool:
stack=[]
for x in s:
if stack:
if stack[-1] == '(' and x == ')':
stack.pop()
elif stack[-1] == '[' and x == ']':
stack.pop()
elif stack[-1] == '{' and x == '}':
stack.pop()
else:
stack.append(x)
else:
stack.append(x)
if stack:
return False
else:
return True
from collections import deque
class MyQueue:
def __init__(self):
self.stack_A, self.stack_B = [], []
def push(self, x: int) -> None:
self.stack_B.append(x)
def pop(self) -> int:
if self.stack_A:
return self.stack_A.pop()
else: #stack_B
while self.stack_B:
self.stack_A.append(self.stack_B.pop())
return self.stack_A.pop()
def peek(self) -> int:
if self.stack_A:
return self.stack_A[-1]
else: #stack_B
while self.stack_B:
self.stack_A.append(self.stack_B.pop())
return self.stack_A[-1]
def empty(self) -> bool:
if not self.stack_A and not self.stack_B:
return True
else:
return False
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
๐งก 0020) stack์ ํ์ฉํด validํ ์ง ์์๋ณด๋ ๋ฌธ์ . stack์ pop()๊ณผ [-1] indexing์ผ๋ก O(1) ๋น ๋ฅธ ์ฐ์ฐ์ ํ์ฉํด ๊ดํธ์ ์์ด ์ ์ ํ ๋งค์นญ๋์๋์ง ์ฝ๊ฒ ๊ตฌํ ์ ์๋ค.
๐งก 0232) Queue๋ ๋ ๊ฐ์ stack์ ํ์ฉํด ๋ง๋ค ์ ์๋ค. ์๋ ๊ทธ๋ฆผ์ ์ฐธ์กฐ.
: stack ๋ ๊ฐ๋ฅผ queue๋ก ์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๋ง๋ค ์ ์๋ค. ๋ค๋ง, stack_A ์ ๋ถ๋ถ stack์ reverseํ ๊ฒฐ๊ณผ์ stack_B๋ฅผ ๊ทธ๋๋ก ๋ถ์ธ ๊ฒฐ๊ณผ๊ฐ queue. queue์ append()ํ ๊ฑด stack_B์ append() ์ฐ์ฐ๊ณผ ๋์ผ. queue ๋งจ ์ผ์ชฝ peek๊ณผ pop์ stack_A๋ฅผ stack_A[-1] indexing๊ณผ pop() ์ฐ์ฐ๊ณผ ๋์ผ.
0217. Contains Duplicate / 0013. Roman to Integer
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
if len(set(nums)) != len(nums):
return True
else:
return False
class Solution:
def romanToInt(self, s: str) -> int:
dct=dict()
dct['I']=1
dct['V']=5
dct['X']=10
dct['L']=50
dct['C']=100
dct['D']=500
dct['M']=1000
ans=0
for x in range(len(s)):
if x>=1:
if s[x-1] == 'C' and s[x] in ['M','D']:
ans+=(dct[s[x]]-200)
continue
elif s[x-1] == 'I' and s[x] in ['V','X']:
ans+=(dct[s[x]]-2)
continue
elif s[x-1] == 'X' and s[x] in ['C','L']:
ans+=(dct[s[x]]-20)
continue
ans+=dct[s[x]]
return ans
๐งก 0217) duplicate ํ์ฉ ์ฌ๋ถ๋ set ์๋ฃ๊ตฌ์กฐ ํ์ฉ
๐งก 0013) I, C, X ์์ธ ์ผ์ด์ค๋ง ๊ฐ๊ฐ ์์ ์๋ ๋ฌธ์์ ๋ฐ๋ผ dict[]์ ๊ฐ์ ์ผ์ ์ ๋งํผ ๋นผ์ฃผ๊ณ , ๋๋จธ์ง์ ๊ฒฝ์ฐ๋ ์ผ์ ์๋ฅผ dictionary์ value๋ก ๋ํด์ฃผ๋ฉด ๋๋ค.
0009. Palindrome Number / 0409. Longest Palindrome
class Solution:
def isPalindrome(self, x: int) -> bool:
x=''.join(str(x))
if x==x[::-1]:
return True
else:
return False
from collections import Counter
class Solution:
def longestPalindrome(self, s: str) -> int:
ans=0
odd_exists = False
freq = Counter(s)
for x in freq:
if freq[x]%2==0:
ans+=freq[x]
else:
odd_exists = True
ans+=(freq[x]-1)
if odd_exists:
ans+=1
return ans
๐งก 0009) ์ฃผ์ด์ง ๋ฌธ์์ด Palindrome์ผ๋ก ์ข์ฐ ๋ค์ง์ผ๋ฉด ๋
๐งก 0409) Counter ํจ์๋ฅผ ํ์ฉํ์ฌ ์ฃผ์ด์ง ๋ฌธ์์ด์ frequency dictionary ์์ฑ. ์ต๋ํ ๊ธด ๊ธธ์ด์ palindrome์ ๋ง๋ค๋ ค๋ฉด ์ฃผ์ด์ง frequency dictionary์์ ์ง์ ๊ฐ์์ frequency๋ ๋ฐ๋ก add up. ํ์ ๊ฐ์์ frequency๋ -1 ํ๊ณ add up. ๋ง์ฝ ํ์ ๊ฐ์์ ๋ฌธ์๊ฐ ์กด์ฌํ๋ค๋ฉด, ์ค์์ 1๊ฐ ๋ฌธ์๋ฅผ ๋์ ์ ์์ผ๋ฏ๋ก +1.
0383. Ransom Note / 0242. Valid Anagram
from collections import Counter
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
ransomNote_Counter = Counter(ransomNote)
magazine_Counter = Counter(magazine)
magazine_Counter_keys = magazine_Counter.keys()
for letter in ransomNote_Counter:
if letter not in magazine_Counter_keys:
return False
else:
if ransomNote_Counter[letter] > magazine_Counter[letter]:
return False
return True
from collections import Counter
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
s_freq = Counter(s)
t_freq = Counter(t)
s_freq_keys = s_freq.keys()
t_freq_keys = t_freq.keys()
if s_freq_keys != t_freq_keys:
return False
for s_freq_key in s_freq_keys:
if s_freq[s_freq_key] != t_freq[s_freq_key]:
return False
return True
๐งก 0383) ransomNote์ freq dictionary์ magazine์ freq dictionary๋ฅผ ๋ชจ๋ ๊ตฌํ๋ค. ์ดํ ransoeNote_Counter์ key๊ฐ magazine_Counter์ ์กด์ฌํ์ง ์๊ฑฐ๋, ์กด์ฌํ๋๋ผ๋ ransomNote_Counter์ key์ ํด๋นํ๋ value๊ฐ magazine_Counter์ key์ ํด๋นํ๋ value๋ณด๋ค ํฌ๋ค๋ฉด magazine์ผ๋ก ๋ ์ด์ ๋ง๋ค ์ ์์ผ๋ฏ๋ก False. ๊ทธ ์ธ์ ๊ฒฝ์ฐ๋ magazine์ผ๋ก ๋ง๋ค ์ ์์ผ๋ฏ๋ก True
๐งก 0242) anagram์ ์ฌ๋ถ๋ ๋ ๋ฌธ์์ด์ Counter ๊ฒฐ๊ณผ๋ก ๋ง๋ค์ด์ง frequency dictionary ์ผ์น ์ฌ๋ถ๋ก ์ ์ ์๋ค. keys๊ฐ ์๋ก ์ผ์นํ์ง ์์ผ๋ฉด ๋น์ฐํ False. ์๋ก ์ผ์นํ๋๋ผ๋ ๋น๋์๊ฐ ๋ค๋ฅด๋ฉด ๋ง๋ค ์ ์์ผ๋ฏ๋ก(ex ab์ aabb) ๋น๋์๊ฐ ํ๋๋ผ๋ ๋ค๋ฅด๋ค๋ฉด ๋ฐ๋ก False ๋ฆฌํด. ๋ชจ๋ for๋ฌธ์ ๋ค ๊ฑฐ์ณค๋ค๋ ๊ฑด True์ด๋ฏ๋ก True ๋ฆฌํด
0136. Single Number / 0069. Sqrt(x)
from collections import Counter
class Solution:
def singleNumber(self, nums: List[int]) -> int:
freq = Counter(nums)
for x in freq:
if freq[x] == 1:
return x
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0: return 0
elif x == 1: return 1
start,end=1,x
while start<=end:
mid=(start+end)//2
if x<mid*mid:
end=mid-1
elif x==(mid*mid):
return mid
else:
ans=mid
start=mid+1
return ans
๐งก 0136) ๋น๋์ 1์ธ ๊ฒฝ์ฐ Counter๋ก ๋๋ฆฌ๋ฉด ๋จ.
๐งก 0069) x์ sqrt(x)๋ฅผ ๊ตฌํ๋ ๋ฌธ์ . ์ง์ O(n)์ผ๋ก brute-force๋ก ๋๋ ค๋ ๋๋, O(logn)์ผ๋ก binary search ํ์ด๋ ๊ฐ๋ฅ. start์ end๋ฅผ ๊ฐ๊ฐ 1๊ณผ x๋ก ์ก๊ณ ์ค๊ฐ mid๋ฅผ ์ ๊ณฑํ ๊ฒฐ๊ณผ๊ฐ x๋ณด๋ค ํฐ ์ง, ๊ฐ์ ์ง, ์์ ์ง์ ๋ฐ๋ผ ์ฒ๋ฆฌํ๋ ๋ฌธ์ .
0374. Guess Number Higher or Lower / 0035. Search Insert Position
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
# 1 if num is lower than the picked number
# otherwise return 0
# def guess(num: int) -> int:
class Solution:
def guessNumber(self, n: int) -> int:
start,end=1,n
while start<=end:
mid=(start+end)//2
if guess(mid) == 0:
return mid
elif guess(mid) == 1:
start=mid+1
else:
end=mid-1
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
start,end=0,len(nums)-1
ans=len(nums)
while start<=end:
mid=(start+end)//2
if nums[mid] == target:
return mid
elif nums[mid] > target:
ans=mid
end=mid-1
else:
start=mid+1
return ans
๐งก 0374) predefined ๋์ด ์๋ guess() ํจ์๋ฅผ ํ์ฉํด 1๋ถํฐ n๊น์ง์ ์ ์ค ์์๋ก ๊ณ ๋ฅธ ์๋ณด๋ค up, same, down์ธ์ง์ ๋ฐ๋ผ ํ์ ๋ฒ์ ์ ๋ฐ์ผ๋ก ์ค์ฌ๊ฐ๋ฉฐ ํ์ธ. ํ์ ๋ฒ์ ์ ๋ฐ์ผ๋ก ์ค์ฌ๊ฐ๋ฉฐ(์ด๋ถํ์) target ํ์ํ๋ฏ๋ก ์๊ฐ๋ณต์ก๋๋ O(logn)
๐งก 0035) ์ฃผ์ด์ง ์ค๋ฆ์ฐจ์ ๋ฐฐ์ด์์ target์ด ์ด๋ ์์น์ ๋ค์ด๊ฐ ์ง index๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ . start์ end๋ฅผ index 0๊ณผ index len(nums)-1๋ก ์ค์ ํ๊ณ ๊ทธ ์ ๋ฐ index์ ํด๋นํ๋ ์์๋ณด๋ค target์ด ํฐ์ง/์์์ง/๊ฐ์์ง์ ๋ฐ๋ผ binary search ์งํ. ์ด ๋, target์ด ์ ์ฒด list์ ์ต๋๊ฐ(๋งจ ์ค๋ฅธ์ชฝ ๊ฐ)๋ณด๋ค ํฌ๋ค๋ฉด default๋ก ๊ธธ์ด๊ฐ ์ถ๋ ฅ๋๊ฒ๋, ans = len(nums)๋ก ์ค์ .
0278. First Bad Version / 0121. Best Time to Buy and Sell Stock
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
def firstBadVersion(self, n: int) -> int:
if n == 1: return 1
start,end=1,n
while start<=end:
mid=(start+end)//2
if isBadVersion(mid):
ans=mid
end=mid-1
else:
start=mid+1
return ans
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
cur_min = prices[0]
for price in prices[1:]:
ans = max(ans,price-cur_min)
if price<cur_min:
cur_min=price
return ans
๐งก 0278) start์ end๋ฅผ ๊ฐ๊ฐ 1๊ณผ n์ผ๋ก ๋๊ณ , mid์ isBadVersion() ๊ฒฐ๊ณผ์ ๋ฐ๋ผ update. ๊ฐ์ฅ ์ฒซ๋ฒ์งธ BadVersion์ ๋ฒํธ๋ฅผ ๊ตฌํ๋ฏ๋ก isBadVersion์ด ๋ง์ ๋ ans = mid ์ค์
๐งก 0121) DP ๋ฌธ์ ๋ก, prices list๋ฅผ for๋ฌธ์ผ๋ก ๋๋ฆฌ๋ฉด์ ์์ list์ ์ต์๊ฐ update. ํ์ฌ ์์์ ์์น index๊ฐ i๋ผ๋ฉด index 0 ~ (i-1)๊น์ง ํด๋นํ๋ ์์ ์ค์ ์ต์๊ฐ์ด prices[i]๋ณด๋ค ์๋ค๋ฉด ans update(์ด ๋ ans๋ ์ต๋๊ฐ ์ ์ง). ์๋ถํฐ ๋๊น์ง ๋์ ํด์ ๊ฒฐ๊ณผ๋ฅผ updateํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ฏ๋ก bottom-up DP
0070. Climbing Stairs / 0733. Flood Fill
class Solution:
def climbStairs(self, n: int) -> int:
dp=[0]*(n+1)
if n == 1:
return 1
else:
dp[1],dp[2]=1,2
for x in range(3,n+1):
dp[x] = dp[x-2]+dp[x-1]
return dp[n]
from collections import deque
def BFS(graph, visited, start,color):
m,n=len(graph),len(graph[0])
start_color = graph[start[0]][start[1]]
graph[start[0]][start[1]] = color
queue = deque([start])
visited[start[0]][start[1]] = True
dx,dy=[-1,1,0,0],[0,0,-1,1]
while queue:
v=queue.popleft()
for i in range(4):
nx,ny=v[0]+dx[i],v[1]+dy[i]
if 0<=nx<m and 0<=ny<n:
if not visited[nx][ny] and graph[nx][ny] == start_color:
visited[nx][ny] = True
graph[nx][ny] = color
queue.append((nx,ny))
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
visited=[[False]*len(image[0]) for _ in range(len(image))]
BFS(image,visited,(sr,sc),color)
return image
๐งก 0070) bottom-up DP ์ ํ์ผ๋ก, n๊ฐ์ step์ ๊ฑด๋๋๋ฐ 1๊ฐ ๋๋ 2๊ฐ์ step์ ์ฌ์ฉํด ๊ฑด๋๋ ๊ฐ์ง์๋ฅผ ๊ตฌํ๋ ์ ํ. dp[n]์ n๊ฐ์ ๊ณ๋จ์ผ๋ก ๊ฑด๋๋ ๊ฐ์ง์๋ผ๋ฉด, ์ ํ์์ dp[n] = dp[n-1] + dp[n-2]๋ก ์ฝ๊ฒ ๋ด๋ฆด์ ์๋ค(n≥3)
๐งก 0733) flood-fill ์ ํ์ผ๋ก, ์์์ ๋ถํฐ ๋์ผํ ๋ถ๋ถ๋ง ์ฃผ์ด์ง color๋ก ์น ํด์ฃผ๋ฉด ๋๋ค. dx,dy๋ก ๋ฐฉํฅ๋ฒกํฐ๋ง๋ค์ด์ simulation ๋๋ฆฌ๋ฉด์ BFS ํ์์ผ๋ก '์กฐ๊ฑด์ ๋ง๋' ์ธ์ ๋ ธ๋๋ง ๋์ผ color๋ก ์ฑ์๋๊ฐ๋ฉด ๋๋ค.
0463. Island Perimeter / 0844. Backspace String Compare
from collections import deque
def BFS(graph, visited, start):
perimeter = 0
queue = deque([start])
visited[start[0]][start[1]] = True
dx,dy=[-1,1,0,0],[0,0,-1,1]
while queue:
vx,vy = queue.popleft()
near_islands=4
for i in range(4):
nx,ny=vx+dx[i],vy+dy[i]
if 0<=nx<len(graph) and 0<=ny<len(graph[0]):
if graph[nx][ny] == 1:
near_islands-=1
if not visited[nx][ny]:
visited[nx][ny] = True
queue.append((nx,ny))
perimeter+=near_islands
return perimeter
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
row,col=len(grid),len(grid[0])
visited=[[False]*col for _ in range(row)]
for i in range(row):
for j in range(col):
if grid[i][j] == 1:
return BFS(grid,visited,(i,j))
def get_stack(string):
stack = []
for s in string:
if s == '#':
if stack: stack.pop()
else:
stack.append(s)
return stack
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
after_s = get_stack(s)
after_t = get_stack(t)
if after_s == after_t:
return True
else:
return False
๐งก 0463) ์ฐ๊ฒฐ์์ญ์ ๋๋ ๋ฅผ ๊ตฌํ๋ ๋ฌธ์ . ๊ฐ๋ฅ near_islands = 4๋ผ ์ค์ ํ ๋ค, ์ฃผ์ ๊ฐ ์ ์๋ ๊ณณ ์์ ๋๋ง๋ค -1. 4๋ฐฉํฅ ๊ฐ๊ฐ ํ์ธ ๋ค update๋ near_islands ๊ฐ์ perimeter์ ๊ณ์ add up.
๐งก 844) ์คํ ๋ฌธ์ . #์ด ์๋ค๋ฉด stack์ ๋ฌด์์ด ์์ ๊ฒฝ์ฐ ๋ฐ๋ก pop(). backspace๋ก ๋ชจ๋ ์ง์ฐ๊ณ ๋ ํ ๊ฐ์์ง ๋ค๋ฅธ ์ง ์๋ก ๋น๊ตํ๋ฉด ๋
'LeetCode Problems > Easy' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๐ LeetCode Easy Collections III - 1 Problems (0) | 2025.01.29 |
---|---|
๐ LeetCode Easy Collections II - 20 Problems (1) | 2024.09.02 |
๋๊ธ