엔지니어 블로그

문제내용주어진 문자열 s를 파티션으로 나누면 되는 문제입니다. 여기서 파티션을 구분짓는 기준은 파티션 내 문자들이 각 파티션에서 최대 한번만 노출되어야합니다.풀이각 문자별로 for문을 이용하여 파티션 끝 값을 파악한 후에 해당 파티션 내 문자의 파티션이 가지고있는 파티션 범위가 포함되는지 확인한 후 길이를 반환하는 식으로 풀이했습니다.class Solution: def partitionLabels(self, s: str) -> list[int]: list = [0] * 26 #1.각각의 글자가 마지막으로 출현한 index를 파악한다. for i,char in enumerate(s): list[ord(char) - ord('a')] = i ..

풀이배열 내의 단어들이 Anagrams인 것들 끼리 묶어서 2차원 배열을 리턴하면 되는 문제다.for문을 이용해서 각각의 요소를 정렬한 후 dict 내에 sorted_str : [str1,str2] 와 같은 형태로 저장하고 value 값들을 list에 담아 리턴하는 형식으로 문제를 풀었다. 코드class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: dict = {} ans = [] for str in strs: sort_str = "".join(sorted(str)) if sort_str in dict.keys(): ..

풀이문제는 생각보다 간단하다. 다양한 종류의 괄호가 있고 이 괄호들이 문자열 s 안에 있을때 제대로 닫혀있는지 확인하면 되는 문제였다. 이전에 문제를 풀면서 너무 깊게 생각하면 자꾸 산으로 가는 경향이 있던 것을 떠올려 쉽게 쉽게 생각하기로 했다. 우선 각각의 괄호 값을 매핑한 dict를 생성한 후 s 의 값을 하나씩 list에 담아가면서 닫혀있는지 확인하는 식으로 진행하는 것으로 방향을 잡았다. 코드class Solution: def isValid(self, s: str) -> bool: stack = [] str_dict = {'{':'}','[':']','(':')'} for str in s: if str in str_dict.value..

풀이이 문제는 s가 t에 속하는지 판별하는 문제다. 단순히 속하는지 여부만 확인하는 것이 아니고, s의 문자 배열 순서가 t에서도 동일해야한다. 무턱대고 t에 속한 s의 문자들을 지웠다가 실패를 맛봤다.two pointer를 사용하기로 했다. i와 j를 두고 s[i] 가 t[j] 와 같다면 list에 추가한 후 s와 동일한지 확인하도록 구성했다. 코드class Solution: def isSubsequence(self, s: str, t: str) -> bool: i = 0 ans = [] for j in range(len(t)): if i >= len(s): break if s[i] == t[j..

풀이기존에 for문을 중첩해서 사용하는 방법으로 문제를 풀었다. 정답은 됐지만 상당히 속도가 느린 정답이 되어 효율적인 방법을 고민해보았고, hash table을 사용하여 새롭게 문제를 풀었다. 물론 아이디어는 떠올려냈지만 구현은 솔루션을 살-짝 컨닝했다 ㅎ 코드class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hash_dict = {} for i,num in enumerate(nums): if target - num in hash_dict: return [i,hash_dict[target-num]] hash_dict[nu..

풀이배열 B에 배열 A의 원소 값이 몇번이나 포함되어 있는지 확인하면 되는 문제다.이 문제는 처음에 for문을 가지고 간단히 구현해봤는데, 정답은 맞았지만 2번의 for문으로 인해 복잡도가 높아져 응답시간이 느린 코드가 되었다. 그래서 솔루션을 살짝 보니 훨씬 간단한 방법이 있었다. 코드#정답코드class Solution: def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]: n = len(A) ans = [] seen = [0] * (n + 1) common = 0 for i in range(n): if seen[A[i..

풀이words2 의 글자가 words1에 포함되어있는지 확인하면 된다.hash table을 사용하는 것으로 생각하고 문제를 풀었다.사실 기존에 list를 통해 해결하려고 했지만 도저히 풀수가 없어서 hash로 사고를 전환하여 풀었다. 1.words2의 글자들로 출현 빈도가 저장된 hash table을 만든다.2.words1의 단어의 글자들의 출현빈도가 저장된 hash table을 만든다.3.두 hash table을 비교한다. 간단하지만 고민하여 푸는데 시간이 꽤나 소요되었다. 하루하루 문제를 푸니 Medium도 손을 델 순 있는 수준이 되어 가는 것 같아 기분이 좋다. 코드from collections import Counterclass Solution: def wordSubsets(self, wo..

풀이주어진 배열 nums 내 각각의 원소들의 차가 k 만큼인 pair의 수를 구하면 된다.int로 초기화 된 dict를 선언한 후 배열 내 값에서 k를 뺴거나 더한 값을 각각 tmp,tmp2에 저장한다.이후 선언해둔 dict에 차가 k 인 pair를 저장하여 그 수를 확인할 수 있게 된다. 코드class Solution: def countKDifference(self, nums: List[int], k: int) -> int: dict = defaultdict(int) cnt = 0 for num in nums: tmp, tmp2 = num+k, num-k if tmp in dict: cnt +=..