본문 바로가기

프로그래밍22

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.
leetcode 5. Longest Palindromic Substring 풀이 문제 : 주어진 문자열에서 가장 긴 대칭하는 substring을 반환하라 Follow up : - 아이디어 : 주어진 문자열을 길이가 1 2021. 4. 13.

티스토리툴바