코딩테스트를 준비하다보니 ... Medium을 제안 받았던만큼 스스로 풀었던 문제 복기를 좀 해볼까 한다.
혹시나 싶어 코드를 보고 싶으신 분이라면 문제 번호나 타이틀로 검색하시면 좋을 것 같습니다.
238. Product of Array Except self
풀이시간은 박살났지만 ..... 아이디어로는 dp 2개 (left_product, right_product) 2개 만들어서 교차 곱셈
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
dp_left = [1 for _ in range (0, len(nums) + 1)]
dp_right = [1 for _ in range (0, len(nums) + 1)]
for i in range (1, len(nums) + 1):
dp_left[i] *= (dp_left[i-1] * nums[i-1])
dp_right[-1-i] *= (dp_right[-i] * nums[-i])
answer = []
347. Top K Frequent Elements
아이디어로는 defaultdict으로 나타낸 뒤에, items을 활용해 tuple 형태로 이를 저장 한다
그 뒤에는 빈도수로 정렬하면 okay
from collections import defaultdict
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
cnt = defaultdict(int)
for num in nums:
cnt[num] += 1
frequent = []
for x, y in cnt.items():
frequent.append([x,y])
frequent.sort(key = lambda x: (-x[1], x[0]))
answer = []
for num_tuple in frequent:
answer.append(num_tuple[0])
return answer[:k]
454. 4 Sum II
O(N^2)이냐, O(N^3)인가가 차이가 나오게 된다. (덧셈의 tuple을 어떻게 짜느냐에 따라)
from collections import defaultdict
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
sum_12 = defaultdict(int)
sum_34 = defaultdict(int)
for num1 in nums1:
for num2 in nums2:
sum_12[num1 + num2] += 1
for num3 in nums3:
for num4 in nums4:
sum_34[num3 + num4] += 1
cnt = 0
for x, y in sum_12.items():
cnt += y * sum_34[(-1) * x]
return cnt
53. Maximum Subarray
합이 최대인 subarray를 찾아내야한다.
이름이 뭐였더라. 카데인 알고리즘이었던 것 같다. curr_max에 현재까지 최대인 것 저장해나가면서 풀면 된다.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
curr_max = 0
answer = -int(1e9)
for num in nums:
curr_max = max(num, curr_max + num)
answer = max(answer, curr_max)
return answer
54. Spiral Matrix
주어진 2차원 matrix에서 외곽을 따라서 숫자를 보관해주면 된다.
총 네방향으로 움직일 수 있고, 방향을 바꾸는 것은
i) 행렬의 끝에 도달했을 때
ii) 현재 방향으로 앞으로 한번 더 나갔을 때, 이미 방문했던 곳에 도착할 때
이때 방향을 바꿔주면 되겠다
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
movement_x = [0,1,0,-1]
movement_y = [1,0,-1,0]
visited = [[False for _ in range (0, len(matrix[0]))] for _ in range (0, len(matrix))]
cnt, direction = 0,0
answer = []
x, y = 0, 0
while cnt != len(matrix[0]) * len(matrix):
answer.append(matrix[x][y])
print(matrix[x][y])
visited[x][y] = True
nx, ny = x + movement_x[direction % 4], y + movement_y[direction % 4]
if (0 > nx or nx >= len(matrix) or 0 > ny or ny >= len(matrix[0])) or (visited[nx][ny] == True):
direction += 1
nx, ny = x + movement_x[direction % 4], y + movement_y[direction % 4]
x, y = nx, ny
cnt += 1
return answer
48. Rotate Image
주어진 정사각행렬을 오른쪽으로 한바퀴 돌리면 되는건데, 이건 두스텝으로 풀어낼 수 있다.
첫번째로 Transpose를 해서 행렬을 전치시킨다.
두번째로 행을 고정시킨 뒤, 열을 반전 시키는 방식으로 풀면 되겠다.
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
#처음에는 transpose
n = len(matrix)
for i in range (0, n):
for j in range (i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
#전후 반전
for i in range (0, n):
for j in range (0, n // 2):
matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
print(matrix)
78. Subsets
주어진 집합의 모든 부분집합을 구해주면 되겠다.
Backtracking의 typical한 문제가 되겠다. 항상 stack에서 pop 해주는 것을 잊지말자.
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
curr_subset = []
def backtracking(n):
result.append(curr_subset.copy())
for i in range(n, len(nums)):
curr_subset.append(nums[i])
backtracking(i+1)
curr_subset.pop()
backtracking(0)
return result
46. Permutations
또 항상 나오는 backtracking.
이럴때는 방문처리를 꼭 해주는 것이 현명하다.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
curr_subset = []
visited = [False for _ in range (0, len(nums))]
def backtracking(n):
if n == len(nums):
result.append(curr_subset.copy())
return
else:
for i in range (0, len(nums)):
if visited[i] == False:
visited[i] = True
curr_subset.append(nums[i])
backtracking(n + 1)
curr_subset.pop()
visited[i] = False
backtracking(0)
return result
215. Kth Largest Element in an array
Array에서 K번째로 큰 원소를 찾으면 된다 굉장히 직관적인 문제.
Heap을 사용하면 비교적 간단하게 풀 수 있다. 처음에 K사이즈짜리 heap을 준비해주고, 새로운 것을 넣느냐 마느냐 식으로 진행하면 되겠다.
class Solution:
import heapq
def findKthLargest(self, nums: List[int], k: int) -> int:
x = nums[:k]
heapq.heapify(x)
for i in range (k, len(nums)):
y = heapq.heappop(x)
if y >= nums[i]:
heapq.heappush(x, y)
else:
heapq.heappush(x, nums[i])
return heapq.heappop(x)
49. Group Anagrams
같은 스펠링이 들어간 단어들을 하나로 그룹으로 묶으면 되겠다.
defaultdict으로 묶어주는 것이 가장 간편하다고 느껴졌다.
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
word_list = defaultdict(list)
for word in strs:
spelling = []
for i in range (len(word)):
spelling.append(word[i])
spelling.sort()
spelling = tuple(spelling)
word_list[spelling].append(word)
return list(word_list.values())
200. Number of Islands
BFS / DFS로 정평이 난... 문제들이다.
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
#bfs
n, m = len(grid), len(grid[0])
visited = [[False for _ in range (m)] for _ in range(n)]
cnt = 0
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
for i in range (n):
for j in range (m):
if grid[i][j] == "1" and visited[i][j] == False:
cnt += 1
lands = deque()
lands.append([i,j])
while lands:
land = lands.popleft()
x, y = land[0], land[1]
if visited[x][y] == False:
visited[x][y] = True
for k in range (0, 4):
nx, ny = x + dx[k], y + dy[k]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == False and grid[nx][ny] == "1":
lands.appendleft([nx, ny])
return cnt
17. Letter combinations of a Phone number
자주 나오는 백트래킹 문제...였는데, 이 경우에는 corr_sym에 핸드폰 자판에 해당되는 것으로 만들어두었다.
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
corr_sym = [[], [], ['a', "b", "c"], ["d", "e", "f"],
["g", "h", "i"], ["j", "k", "l"], ["m", "n", "o"], ["p", "q", "r", "s"], ["t", "u", "v"],
["w", "x", "y","z"]]
answer = []
curr_word = []
if digits == "":
return []
def backtracking(n):
if n == len(digits):
word = "".join(string for string in curr_word)
answer.append(word)
return
for spelling in corr_sym[int(digits[n])]:
curr_word.append(spelling)
backtracking(n+1)
curr_word.pop()
backtracking(0)
return answer
287. Find the Duplicate Number
중복이 되는 숫자가 뭐냐? 라고 물어보는 상황이었기에 defaultdict으로 카운팅
from collections import defaultdict
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
check = defaultdict(int)
for num in nums:
if check[num] == 0:
check[num] = 1
else:
return num
300. Longest Increasing Subsequence
최장 증가 수열 (Strictly한)을 찾는 것이다.
1차원 dp문제로 기억하고 있다.
이전 값들과 비교해나가면서 큰지 어떤지 계산해주면 되겠다.
그래서 거의 O(N**2) 정도로 되는 것으로 받아들일 수 있다. (아마 N**2보다는 작겠지만)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
#Strictly increasing
n = len(nums)
dp = [1 for _ in range (n)]
max_length = 1
for i in range (0, n):
for j in range (0, i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
max_length = max(max_length, dp[i])
return max_length
22. Generate Parenthese
마치 적절한 괄호 갯수를 카운팅해보세요. or 구현해보세요.
같은 문제입니다. 백트래킹 / 브루트포스에 가까운 문제라고 생각되네요.
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
#원래 있던 거에 씌우거나 / 2개를 합치거나
dp = [[] for _ in range (n + 1)]
dp[1] = ["()"]
for i in range (2, n + 1):
for parent in dp[i-1]:
dp[i].append("(" + parent + ")")
for j in range (1, i // 2 + 1):
for parent1 in dp[i-j]:
for parent2 in dp[j]:
dp[i].append(parent1 + parent2)
dp[i].append(parent2 + parent1)
dp[i] = list(set(dp[i]))
return dp[-1]
210. Course Schedule II
아마 위상 정렬 그래프였던가? 그런 이름이었던 것으로 기억한다.
그래프의 끝점 (indegree가 0인 점)부터 시작해주면서, indegree가 0이 되면 deq에 넣어주는 형식이다.
from collections import deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
answer = []
ind = [0 for _ in range (0, numCourses)]
course = [[] for _ in range (0, numCourses)]
for pre in prerequisites:
a,b = pre[0], pre[1]
ind[b] += 1
course[a].append(b)
deq = deque()
for i in range (0, numCourses):
if ind[i] == 0:
deq.append(i)
while deq:
x = deq.popleft()
answer.append(x)
for y in course[x]:
ind[y] -= 1
if ind[y] == 0:
deq.append(y)
if len(answer) != numCourses:
return []
return answer[::-1]
240. Search a 2D Matrix II
2차원 배열에서 찾고자 하는 target이 있는지 확인하는 방법
처음 알게 된건데, any를 활용하는 방법이 있다는 것을 알게 되었다.
계산 시간도 굉장히 좋다.
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
return any(target in row for row in matrix)
