배고픈 개발자 이야기

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))..

Easy난이도 Acceptence 46.8% 문제 더했을때 target값이되는 nums의 원소 2개의 인덱스를 리스트로 반환하는 문제로 앞쪽 원소부터 찾아 정답을 구하도록 하였다. class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ for i, x in enumerate(nums): for j in range(len(nums) - i - 1): if target == nums[i] + nums[i + j + 1]: return [i, i + j + 1]

Easy난이도 Acceptence 48.7% 문제 입련된 Tree의 root node를 중심으로 왼쪽과 오른쪽이 거울처럼 뒤집었을 때 같은지를 검증하는 문제다. 문제에 root 노드는 반드시 존재하므로 compare함수에 left와 right 노드를 넣어 비교하였다. compare함수는 입력된 양쪽 노드를 비교하는 함수로 둘다 없으면 참으로 값이나 노드가 다를 경우 불로 판정하도록 만들었다. class Solution(object): def compare(self, lNode, rNode): if lNode == None and rNode == None: return True if lNode == None or rNode == None: return False if lNode.val != rNode.va..

Easy난이도 Acceptence 66.8% 문제 주어진 input에 유니크한 숫자를 반환하는 문제로 파이썬 리스트의 count 함수를 사용, 갯수가 1개만 있는 원소를 반환하였다. class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ for num in nums: if nums.count(num) == 1: return num

Easy난이도 Acceptence 56.6%의 문제 이문제는 2개의 정렬된 리스트 노드를 하나의 리스트노드로 정렬하여 반환하는 문제이다. 단순히 둘중하나가 None이면 남은 노드만 처리해주도록 추가하였고 둘다 있을경우 값을 비교하여 output을 만들어 내었다. dummy 노드를 만들어 output에 얕은 복사후 반환하면 reverse함수를 사용하지 않아도 되지만 이번 문제에선 정답으로 만든 output이 tail을 가리키고 있기 때문에 역으로 만들어 반환하였다. class Solution(object): def __init__(self): self.output = None # 검증은 했지만 정확한 원리파악이 필요 def reverse(self): prev = None cur = self.output w..

Easy 난이도 Acceptence 48%의 문제 주어진 리스트에서의 subarray중 합이 최대인 원소의 집합을 구하여 최댓값을 반환하는 문제 class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ # Kadane's Algorithm DP curSum = maxSum = nums[0] for i, num in enumerate(nums[1:]): curSum = max(nums[i+1], nums[i+1] + curSum) maxSum = max(curSum, maxSum) return maxSum