본문 바로가기

프로그래밍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.
leetcode 55. Jump Game 풀이 문제 : int로 이루어진 list의 첫번째 인덱스로 부터 출발한다. 출발점에서 인덱스 + 원소 만큼 점프가 가능하다. list의 끝에 도달할 수 있는지 여부를 boolean으로 반환하라. Follow up : 아이디어 : 시작점과 끝점을 설정해서 해당 구간에서 가장 멀리갈 수 있는 점을 구한다. 다음 탐색을 직전의 끝점 + 1 에서 가장 멀리갈 수 있는 점 까지 하며 마지막 원소에 도달 할 수 있는지 탐색한다. 코드 : class Solution: def canJump(self, nums: List[int]) -> bool: if len(nums) == 1: return True def find(s, e): m = -1 print(s, e) for i in range(s, e): m = max(m, (.. 2021. 4. 20.

티스토리툴바