배고픈 개발자 이야기

Medium 난이도 Acceptence 60.6% 문제 입력으로 주어진 단어 리스트 중에 철자를 바꿨을 때 동일한 문자를 리스트로 묶어서 반환하는 문제이다. 주어진 입렵값의 범위가 크기 때문에 효율적으로 풀어야 좋을것으로 보이나직관적으로 풀이해보았다. -풀이-단어의 철자를 각각 아스키코드로 변환한 후, 정렬 및 중복 제거를 한다.중복제거한 단어열별로 각각 리스트별로 묶는다 (원본 인덱스 사용) class Solution(object): def groupAnagrams(self, strs): """ :type strs: List[str] :rtype: List[List[str]] """ if len(strs)

Medium 난이도 Acceptence 36.2% 문제 끝에서 n번째 노드를 제거하는 문제, 리스트로 값을 바꿔 원하는 노드를 지운 후 다시 노드로 바꿔 문제를 풀었다. 문제에서는 one pass로 풀 수 있냐고 한것에 더 맞는 정답을 위해선 list node class의 remove함수를 따로 구현해야 할것으로 보인다. class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ tempList = [] while head is not None: tempList.append(head.val) head = head.next del tempList[len..

Medium 난이도 Acceptence 50.1% 문제 문재는 핸드폰 번호판에 매핑된 문자를 사용하여 만들 수 있는 모든 문자 조합을 구하는 문제로 먼저, 각 번호를 key 매핑문자를 value로 저장 후, 입력으로 들어온 숫자의 길이에 맞게 순서대로 조합을 생성하여 반환한다. class Solution(object): def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ mapNum = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'} l = len(digits) result = [] if l == 0: retu..

Medium 난이도 Acceptence 66.5% 문제 이진트리를 inorder 순회한 값을 리스트로 반환하는 문제 아래와 같이 left, root right 노드를 재귀로 순회하도록 구성하였고 왼쪽 아래의 노드부터 inorder로 순회하도록 한다. 여기서 extend라는 함수에 대해 찾아봤는데 재귀함수로 값을 더할 경우 extend를 사용, append사용시 원하는대로 값이 더해지지 않는 경우가 많다. class Solution(object): def traverseNode(self, curNode): result = [] if curNode is None: return result if curNode.left is not None: result.extend(self.traverseNode(curNod..

Medium 난이도 Acceptence 35.9% 문제 입력된 listnode 두개는 10진수의 숫자의 역순으로 원래의 두값을 더한 후 다시 역순으로 반환하면 되는 문제다. 더한값 sum과 carry값 및 반환용 dummy로 listnode 얕은복사값 사용 값은 두값 또는 carry값이 있을 경우 계속 계산한다. 해당 자리수의 값을 sum한 후 10의 몫을 carry값, 나머지를 해당자리수의 값으로 계산한다. class Solution(object): def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ c = 0 s = 0 dummy = ListNode() curr = dummy whi..

Medium 난이도 Acceptence 28.4 문제 입력 리스트에서 3개의 원소를 더해 0이 되는 subarray를 구하는 문제, 순서만 다른 subarray는 허용되지 않는다. 처음에 3중 반복문으로 풀려고 했지만 성능이 매우 좋지않아 TimeLimitError가 발생한다, 따라서 최대 2중 반복문 이하의 시간복잡도를 가지도록 풀어야 한다. 우선 입력값을 정렬하였고, 첫 원소부터 마지막 첫번째가 되는 원소까지 반복한다. 루프 시작에 이전 원소와 같아 검사할 필요가 없거나 최소값에 최댓값 2개를 더햇을 경우에도 0이 되지않는 경우를 미리 검사해 필요없는 계산을 하지 않도록 한다. 그리고 0이되는 값을 검사할 땐 quick sort의 값을 찾는 개념으로 왼쪽 pivot과 오른쪽 pivot을 정해 값의 크..

Hard 난이도 Acceptence 30% 문제 입련된 문자열에서 유효한 최대길이의 괄호쌍의 길이를 구하는 문제 문자열의 길이만큼 0으로 문자열을 만들었고, 왼쪽 괄호일경우 인덱스를 더하고, 오른쪽괄호일 경우 왼쪽괄호와 오른쪽괄호 위치의 값을 1로 만든다. 모든 유효한 괄호쌍을 1로 유효하지 않은 괄호는 0으로 저장한 문자열중 1을 max로 가지고 있는 subarray를 정답으로 구한다. class Solution: def longestValidParentheses(self, s): stack = [] a = ['0'] * len(s) for i in range(len(s)): if s[i] == '(': stack.append(i) else: if not stack: next else: index = ..

Easy 난이도 Acceptence 40.1% 문제 괄호의 짝이 맞는지 안맞는지를 판정하는 문제로 리스트를 스택처럼 사용하였다. 괄호 왼쪽일경우 리스트에 더하고 오른쪽일 경우 pop하여 Last in 한값과 비교하도록 하였고 비교값을 Askii 코드 값을 사용하였다. class Solution(object): def __init__(self): self.output = [] self.left = "([{" self.right = ")]}" self.valid = [81, 184, 248] def isValid(self, s): """ :type s: str :rtype: bool """ for word in s: if word in self.left: self.output.append(ord(word))..