본문 바로가기

leetcode 풀이20

지도에서 상하좌우 움직이기 def isOut(x, y): if N >= x > 0 and N >= y > 0 : # print(False) return False # print(True) return True def doAction(action) : global x, y, nx, ny nx = x ny = y if action == "R" : nx +=1 if action == "U" : ny -=1 if action == "D" : ny +=1 if isOut(nx, ny): # print("out", nx, ny) return x, y = nx, ny if __name__=="__main__": # plans = input().split() plans = ['R', 'R', 'R', 'U', 'D', 'D'] N = 5 x, .. 2022. 8. 27.
leetcode 206. Reverse Linked List 만약에 stack을 쓰게 된다면 O(2n)의 시간복잡도와 시간복잡도가 생기기 마련이다. 하지만 우리는 포인터 개념으로 여기에 접근하면 O(n)으로도 풀이가 가능하다 바로 이전에 저장했던 이전 node들을 저장해서 포인터의 방향을 반대로 바꾸는 것이다 코드를 한번 따라가보자 현재 노드를 뜻하는 curr가 2에 있다고 가정하자. 그렇다면 이전 노드를 뜻하는 prev는 1일 것이고, 3은 curr.next 가 될 것이다. 그렇다면 아래의 코드가 이해가 될 것이다 curr.next = prev 현재 curr 노드의 next는 prev 노드로 정한다 라는 뜻이다. 그럼 prev를 이제 현재 노드로 입력을 해두어야 다음 loop를 쓸 것이다 prev = curr 위와 같이 쓸 수 있다. 자 이제 2의 다음 node.. 2022. 4. 5.
leetcode 46. Permutations 순열 https://leetcode.com/problems/permutations/ Permutations - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Example 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,.. 2022. 4. 3.
leetcode 153 - Find Minimum in Rotated Sorted Array 이 문제는 O(logN)으로 풀라고 나와있다. logN으로 주어진 것이면 우리는 binary search라는 것을 직감적으로 알아야한다. 바로 최소값을 찾기 위한 여정을 해야하는데, 안타깝게도 좌로 n번이 회전이 되어있는 array안에서 찾아야한다. 이런 경우에는 우리는 문제에 어떻게 다가갈 것인지 생각을 해봐야한다. 즉 mid로 항상 중앙에 위치한 값을 찾으면서, 역전이 일어난 부분이 있다면 그 부분이 변곡이 일어난 곳이며, 각 최대값 또는 최소값이 해당 mid 주변에 위치해있다는 뜻이다. 완성된 코드는 아래와 같다 class Solution(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) =.. 2022. 3. 28.
leetcode 152 - Maximum Product Subarray class Solution(object): def maxProduct(self, nums): """ :type nums: List[int] :rtype: int """ max_product = nums[0] min_product = nums[0] ans = nums[0] for i in range(1, len(nums)): min_val = min_product*nums[i] max_val = max_product*nums[i] max_product = max(min_val, nums[i], max_val) min_product = min(min_val, nums[i], max_val) ans = max(ans, max_product) return ans 2022. 3. 28.
leetcode 53 - Maximum Subarray 합이 최대가 되는 subarray를 찾고 그 합을 구하는 문제이다. O(n)으로 풀지 않으면 Times Limit Exceeded가 뜬다. 따라서 Brute force로 풀면 array를 탐색하면서 가능한 모든 subarray를 비교하게 될 것이다. 코드는 짧지만 subarray의 합이 최대가 되는 경우를 생각해야 한다. current_sum이라는 값을 두고, max_sum이라는 값을 따로 둔다. current_sum은 이전에 구한 합과 현재의 값을 비교하여 더 큰 값을 저장하는 변수다. max_sum은 첫 번째 값으로 초기화한 뒤 current_sum과 비교해 더 큰 값을 항상 저장한다. current_sum은 현재 index의 값을 포함하는 값 중 최대가 되는 합이고, max_sum은 전체 array.. 2022. 3. 28.
leetcode 238 - Product of Array Except Self 배열을 순회하면서 각 idx에 있는 수를 제외한 나머지들을 모두 곱한 값을 출력하는 문제 게다가 문제에서도 O(n)의 시간복잡도로 풀이를 하라고 되어있다. [1,2,3,4]의 경우는 [ 2*3*4 , 1*3*4, 1*2*4, 1*2*3] 인 [24, 12, 8, 6] 이 답인 것이다. 이는 뒤집에서 생각해보면, [1*2*3*4 / 1 , 1*2*3*4 / 2 , 1*2*3*4 / 3 , 1*2*3*4 / 4] 의 계산으로도 가능하기 때문에, 전체 의 곱인 24를 구하고 각 1,2,3,4로 나누면 되는 것이다. 이때 주의해야 하는 점이 리스트에 0이 포함되는 경우이다. [-1, 1, 0, -3, 3]인 경우, 모든 곱을 하게 되면 0이 나오니 위의 로직을 그대로 따른 다면 [0, 0, 0, 0, 0]이 나.. 2022. 3. 26.
leetcode 217 - Contains Duplicate 굉장히 쉽다 즉 distinct 한지 아닌지만 확인하면 되기 때문에, 배열의 길이와 set(배열)의 길이가 같은지 다른지만 체크하면 OK. class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ if len(set(nums)) == len(nums) : return False return True 2022. 3. 25.
leetcode 121 - Best Time to Buy and Sell Stock 하루에 한번 매매를 할 수 있을 때, 어떻게 하면 저점에 사서, 고점에 팔 수 있는 알고리즘을 짜는 것이다. for loop를 두번 도는 것이 아닌, 매 loop를 돌 때마다 최고 가격과 최저가격을 기록하면 되는 것이므로, 아래와 같이 그냥 O(n)으로도 풀이가 가능하다. class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ import sys profit = 0 min_price = sys.maxsize for price in prices: if price profit : profit = .. 2022. 3. 25.
페이스북 tech lead가 추천하는 leetcode 문제 75 New Year Gift to every fellow time-constrained engineer out there looking for a job, here's a list of the best LeetCode questions that teach you core concepts and techniques for each category/type of problems! Many other LeetCode questions are a mash of the techniques from these individual questions. I used this list in my last job hunt to only do the important questions. Good luck and Happy New.. 2022. 3. 25.

티스토리툴바