본문 바로가기

전체 글50

leetcode 494. Target Sum 풀이 문제 : int 로 이루어진 list가 주어질때 원소들의 +, - 를 통해 target에 도달하는 경우의 수를 반환하라. Follow up : 아이디어 : DFS 를 통해 풀었지만 풀면서도 이거 반드시 timeout 날 것이라 생각했고 역시나 timeout이 발생했다. dictionary 를 통해서 tracking을 해야할거 같은데 명확한 방법이 생각나지 않았다. 코드 : 처음 작성한 코드 class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: global ans ans = 0 def dfs(i, s): global ans print(i, s, ans) if i == len(nums) - 1: if s == tar.. 2021. 4. 22.
leetcode 739. Daily Temperatures 풀이 문제 : int로 이루어진 list가 주어질때, 각 인덱스는 날짜, 원소는 온도를 나타낸다. 각 날짜의 날씨보다 따뜻한 날씨가 되는 날수를 원소로 갖는 list를 반환하라 Follow up : 아이디어 : V 자 형으로 계속 기온이 떨어지다가 올라가게 된다면, 최초의 날짜의 값을 추적하기 용이한 자료구조형을 사용해야할 것이다. 따라서 stack을 사용하여 (인덱스, 온도값) 을 저장하여 인덱스를 이동할때 stack의 top의 온도와 비교하여 더 높으면 pop을 하는 것을 반복한다. pop한 원소의 index와 현재 index를 비교하여 날짜를 계산한다. 코드 : class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: s = [] a.. 2021. 4. 22.
leetcode 64. Minimum Path Sum 풀이 문제 : m x n 으로 이루어진 grid 가 주어질때 (0,0)에서 출발하여 (m-1, n-1) 에 x, y 좌표로 한칸 씩만 이동할 수 있을 때 path에 있는 grid 값의 합이 최소가 되는 (m-1, n-1) 의 값을 반환하라. ex) Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Follow up : - 아이디어 : 처음에는 경로 탐색으로 생각해서 BFS로 풀었지만 input이 커지자 timeout 이 발생했다. 아무래도 dp로 풀어야되는거 같은데 아이디어가 떠오르지 않았다. 코드 : BFS로 푼 timeout이 발생하는 코드 from collections import deque class Solution: def minPathSum(self, grid.. 2021. 4. 22.
leetcode 45. Jump Game II 풀이 문제 : int로 이루어진 list의 첫번째 index에서 시작해서 원소만큼 이동할 수 있을 때. 마지막 원소에 도달하는 최소 횟수를 구하라. (반드시 도달할 수 있는 입력만 주어진다) Follow up : 아이디어 : Jump Game 1 에서 푼 것과 같이 탐색을 진행하며 count 를 증가시킨다. 마지막 원소에 도달하면 count를 return한다. 코드 : class Solution: def jump(self, nums: List[int]) -> int: if len(nums) == 1: return 0 def find(s, e, t): if len(nums) 2021. 4. 21.

티스토리툴바