본문 바로가기

전체 글50

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.
leetcode 39. Combination Sum 풀이 문제 : 중복되지 않는 int 로 이루어진 list 에서 부분집합의 합이 target과 동일한 부분집합의 list를 return하라 ( 부분집합을 생성할 때 동일한 원소를 사용해도 된다.) Follow up : - 아이디어 : 모든 경우의 수를 탐색하면서 특정 값을 찾아야하므로 dfs를 사용하기로 했다. 재귀 형태를 사용하며 탈출조건은 sum과 target이 같아지면 path를 return 하기로 했다. 코드 : class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: global ans ans = [] def dfs(path: List[int], index: int, s: int) -> .. 2021. 4. 20.
leetcode 15. 3Sum 풀이 문제 : 수열 nums 가 주어질때 3개의 원소를 더했을때 0 이 되는 부분 수열을 모두 반환하라. 단 중복되는 것은 하나만 반환한다. Follow up : 문제는 어떻게든 풀었지만 시간과 메모리 사용량이 너무 많다. 다른 좋은 방법이 있을 것으로 예상된다. 아이디어 : 문제에 주어진 수열을 음수와 양수를 나누어서 각각 정렬된 list를 만든다. 경우의 수가 모두 3가지로 1. 0 으로만 이루어진 return 2. 음수에서 2개를 뽑고 양수에서 하나를 뽑는 경우 3. 양수에서 2개를 뽑고 음수에서 하나를 뽑는 경우 이러한 경우를 만든 후, timeout을 방지하기 위해 2개를 뽑아 더한 수의 절대값이 다른 list의 절대값이 가장 큰 원소를 넘는 경우, continue 했다. 코드 : 내가 작성한 코드 .. 2021. 4. 14.
leetcode 17. Letter Combinations of a Phone Number 풀이 문제 : 전화기 2-9 사이 번호에 쓰여진 문자열들의 조합을 반환하라 Follow up : 아이디어 : 각 번호에 해당하는 문자열의 dictionary를 만든 후 문자를 순회하며 반환해야할 리스트에 값을 추가한다. 코드 : class Solution: def letterCombinations(self, digits: str) -> List[str]: ans = [] if not digits: return ans d = {2: ['a', 'b', 'c'], 3: ['d', 'e', 'f'], 4: ['g', 'h', 'i'], 5: ['j', 'k', 'l'], 6: ['m', 'n', 'o'], 7: ['p', 'q', 'r', 's'], 8: ['t', 'u', 'v'], 9: ['w', 'x', 'y.. 2021. 4. 14.

티스토리툴바