본문 바로가기

프로그래밍22

leetcode 213. House Robber II 풀이 문제 : 원형 큐 형태의 list로 집들이 소유한 재산값이 주어질 때, 인접한 집을 동시에 털지 않으면서 최대의 이득을 취한 값을 구하라. Input: nums = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses. Follow up : 아이디어 : 처음에는 dp list를 만들어서 visit을 확인하려했으나 의미가 없었다. 다른 사람의 풀이를 참고하여 풀었을 때, 첫번째 원소와 마지막 원소가 이어지는 부분은 slicing으로 점화식 부분은 list를 순회하며 최대값을 구하는 방식으로 구했다. 코드 : class Sol.. 2021. 5. 3.
leetcode 63. Unique Paths II 풀이 문제 : 0,0에서 시작하여 오른쪽 아래 끝칸으로 한칸씩 이동할때, 장애물 좌표계가 주어진다. 마지막 지점에 도달할 수 있는 unique path의 합을 반환하라 Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right Follow up : 아이디어 : unique path 1번 문제에서 장애물 요소를 추가하면 된다. .. 2021. 5. 3.
leetcode 733. Flood Fill 풀이 문제 : 아래와 같이 최초의 좌표로 부터 같은 값을 가지는 상하좌우에 대해 newColor를 전개한 후 image를 반환하라 Input: image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] Follow up : 아이디어 : floodfill 에 대한 기본적인 문제로 상하좌우를 순회하며 index를 넘어가지 않으면서 값을 전개한다. 코드 : class Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]: n = len(image) m = len(ima.. 2021. 4. 27.
leetcode 139. Word Break 풀이 문제 : 주어진 문자열을 주어진 wordDict의 문자열로 완전히 나눌 수 있는지 여부를 반환하라. Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code". Follow up : 아이디어 : find를 통해 wordDict와 일치하는 문자열의 시작 index를 찾은 후 그것을 기준으로 문자열을 나누어서 재귀로 탐색하려 했다. 하지만 이 경우에는 제대로 된 반환 값을 전달하기 힘든 문제와 시간 복잡도의 증가로 인해 문제를 풀지 못했다. 코드 : 다른 사람이 짠 코드 def wordBreak(self, s, wordD.. 2021. 4. 27.

티스토리툴바