리트코드

문제모든 부분 집합을 리턴하라  · 입출력 예 num_listreturn[1, 2, 3][[3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], []]풀이입력값으로 트리를 구성하고, 트리를 DFS하는 문제로 풀이할 수 있다.경로 (path)를 만들어 나가면서, 인덱스를 1씩 증가하는 형태로 깊이 우선 탐색을 진행하였다. 별도의 종료 조건이 없기 때문에, 탐색이끝나면 저절로 함수가 종료된다. 입력받은 숫자 배열로 만들 수 있는 모든 부분 집합들이 정답이기 떄문에, dfs를 진행할 때마다 결과배열에 값을 추가하고, 이를 반환하는 형태로 문제를 풀었다.

문제중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라  · 입출력 예stringreturn"abcabcbb"3 (abc)"bbbbb"1 (b)"pwwkew"3 (wke)풀이1. 슬라이딩 윈도우와 투 포인터 사이즈 조절def lengthOfLongestSubstring(s: str) -> int: used = {} max_length = start = 0 for index, char in enumerate(s): if char in used and start 투 포인터로 문제를 풀이하였는데, 포인터 2개 모두 왼쪽에서 출발한다. 두 번째 포인터 (index)를 오른쪽으로 확장시켜 나가며 문자열을 검사한다. 문자가 앞서 등장했는지 여부를 판단하고, 등장했을 경우 시작점을..

문제2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라  · 입출력 예digitsreturn"23"["ad", "ae", "af", "bd", "bf", "bf", "cd", "ce", "cf"]풀이1. 모든 조합 탐색-> 가능한 경우를 모두 조합하는 형태로 전체를 탐색한 후 백트래킹하면서 결과를 조합할 수 있다.입력값 digits를 자릿수로 쪼개어 반복하고, 숫자에 해당하는 모든 문자열을 반복하며 문자 단위로 재귀 탐색을 진행한다. 문자를 조합해 만들 수 있는 길이는 입력값의 길이와 동일하므로, 해당 조건을 재귀함수의 종료 조건으로 설정하고, 조건에 맞지 않을 경우 dfs를 반복 수행한다.

문제1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라. (연결되어 있는 1의 덩어리 개수를 구하라) · 입출력 예 grid mapreturn111101101011000000001110001100000100000113풀이1. DFS로 그래프 탐색이와 같이 작성하였을 경우, grid를 dfs 함수 호출시마다 넘겨주어야 하고, 함수 호출 시 매번 self.가 따라 붙는다.  2. DFS로 그래프 탐색 (중첩함수 사용)DFS 탐색을 하는 dfs 함수는 동서남북을 모두 탐색하며 재귀호출한다. 이동하고자 하는 곳이 육지가 아닌 경우에 return 하도록 설정해줌으로써 연결되어 있는 섬을 구할 수 있다. 이 함수에서 이미 방문했던 곳(grid[i][j])은 1이 아닌 값으로 마킹하..

문제매일의 화씨 온도(˚F) 리스트 T를 입력받아, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라  · 입출력 예 T[73, 74, 75, 71, 69, 72, 76, 73]return[1, 1, 4, 2, 1, 1, 0, 0] 풀이1. 스택 값 비교-> 현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교하여, 더 높다면 스택의 값을 pop()으로 꺼내고, 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다.def dailyTemperatures(T: list[int]) -> list[int]: answer = [0] * len(T) stack = [] for i, cur in ..

문제괄호로 된 입력값이 올바른지 판별하라 · 입출력 예 sreturn()[]{}True풀이1. 스택 일치 여부 판별-> 파이썬 리스트는 스택 연산인 푸시와 팝이 O(1)에 동작한다.def isValid(s: str) -> bool: stack = [] table = { ')':'(', '}':'{', ']':'[' } for char in s: if char not in table: stack.append(char) elif not stack or table[char] != stack.pop(): return False return len(stack) == 0매..

문제덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. · 입출력 예 numstargetreturn[2, 7, 11, 15]9[0, 1]풀이1. 브루트 포스로 계산def twoSum(nums: list[int], target: int) -> list[int]: for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j]브루트 포스란 배열을 2번 반복하며 모든 조합을 더해 일일이 확인해보는 무차별 대입 방식으로, 비효율적인 풀이법에 해당한다. nums 배열을 이중 탐색하며 nums[i], nums..

문제가장 긴 팰린드롬 부분 문자열을 출력하라 · 입출력 예 sreturn"babad""bab""cbbd""bb"풀이1. 중앙을 중심으로 확장하는 풀이-> 이 문제는 다이나믹 프로그래밍으로도 풀 수 있지만, 이를 이용한 풀이는 직관적으로 이해하기 어렵고, 실행 속도가 늦다. 이에 투포인터가 중앙을 중심으로 확장하는 형태로 문제를 풀어보자.def longestPalindrome(s: str) -> str: def expand(left: int, right: int) -> str: while left >= 0 and right 가장 먼저 리스트 슬라이싱을 이용한 예외 처리를 해줌으로써 전체적인 풀이 속도를 향상한다. 이후 슬라이딩 윈도우가 문자열 처음부터끝까지 우측으로 이동하며, expand..

문제문자열 배열을 받아 애너그램 단위로 그룹핑하라 * 애너그램이란 ? 일정의 언어유희로, 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 뜻함 · 입출력 예 입력["eat", "tea", "tan", "ate", "nat", "bat"]출력[["ate", "eat", "tea"], ["nat", "tan"], ["bat"]] 풀이1. 정렬하여 딕셔너리에 추가-> 애너그램을 판단하는 가장 간단한 방법은 정렬하여 비교하는 것이다. (애너그램 관계인 단어를 정렬하면 서로 같은 값을 가짐)def groupAnagrams(strs: list[str]) -> list[list[str]]: anagrams = collections.defaultdict(list) for word in strs:..

문제주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다. 입출력 예sreturn"A man, a plan, a canal: Panama'true "race a car"false풀이1. 리스트로 변환def isPalindrome(self, s: str) -> bool: strs = [] for char in s: if char.isalnum(): strs.append(char.lower()) # ['a', 'm', 'a', ...] while len(strs) > 1: if strs.pop(0) != strs.pop(): return False return True영문..