본문 바로가기

leetcode30

Leet code 242 - Valid Anagram 문자열 입력 s,t에 대해 애너그램관계에 있는지 판단 하는 문제이다 나의 풀이 처음에는 해쉬맵을 사용해볼까 했으나, list변환 이후 sort하면 간단히 풀릴 것 같아 list.sort를 활용하였다. class Solution: def isAnagram(self, s: str, t: str) -> bool: # 각 문자의 개수가 일치하는가? # s의 각 문자 개수를 해쉬맵으로 # t의 각 문자 개수를 해쉬맵으로 # 걍 쏘트해서 비교하면 되는거 아님? ls_s = list(s) ls_t = list(t) ls_s.sort() ls_t.sort() return True if ls_s == ls_t else False 2023. 5. 16.
Leet code 104 - Maximum Depth of Binary Tree 첫번째 트리 문제이다.. 처음에는 input이 리스트로 주어지는 줄 알고, 리스트에 null까지 있겠다그냥 단순히 원소 갯수 몇개인지 재귀적으로 나눠주고 +1을 하려햇으나 문제를 잘읽어보면 제일 binary tree node클래스에 대해 정의가 되어 있다. 1. dfs를 이용한 풀이 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: ''' 널도.. 2023. 5. 16.
Leet code 3 - Longest Substring Without Repeating Characters 내 풀이. 브루트 포스를 활용한 풀이 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: dict1 = {} result = 0 cnt = 0 if len(s) == 1 : return 1 for i in range(len(s)): for j in range(i,len(s)): if s[j] in dict1: result = max(cnt, result) cnt = 0 dict1 = {} break cnt += 1 dict1[s[j]] = 0 return result 중복 발생시 시작 인덱스를 바꿔가며 처음부터 세준다. 순회했던 문자열은 후에 다시 탐색하는 시간이 추가적으로 발생하는 것을 막기 위해 해쉬를 사용해 준다. 길이가 1일때는 .. 2023. 5. 15.
leet code 300 - Longest Increasing Subsequence 어려운 dp문제.. 일단 브루트포스로 접근 해보자. [1,2,4,3] 리스트에서, 모든 경우의 수를 판단한다고 해보자. 일단, 0 , 1 , 2 , 3 2^4의 조합. 2^n의 시간복잡도를 보인다. dfs- cache. dfs 풀이. 인덱스 0에서 시작하는 경우, 인덱스 1에서 시작하는 경우, 인덱스 2에서 시작하는 경우, 인덱스 3에서 시작하는 경우가 있다. 0에서 시작하는 경우를 파고 들어가보자. 0 다음에 인덱스 1이 오는 경우, 인덱스 2가 오는 경우 인덱스 3이 오는 경우가 있다. 인덱스 2,3이 온경우는 더 내려가지 못한다. (인덱스 문제, 크기의 문제) 인덱스 1이 온경우는 인덱스 2가 오는 경우와 인덱스 3이 오는 경우 두가지로 나뉜다. 이제 인덱스 3에서 시작하는경우 2에서 시작하는 경.. 2023. 5. 3.

티스토리툴바