Leet Code - Medium 부수기

 

코딩테스트를 준비하다보니 ... 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)