HTTP:! HTTP:!

특정 시점에 주식을 사서 최대 이익을 보면서 파는 문제 사실 for문 두번으로도 접근이 가능하나, 시간 초과가 난다. for문 한번으로 진행하면서 최소값을 찾고, 이후에 최소값을 뺴보면서 최대 수익금을 찾는다. 지나온 시점은 상관이 없으므로 무시한다. def maxProfit(self, prices: List[int]) -> int: profit = 0 _min = sys.maxsize for item in prices: _min = min(_min, item) profit = max(profit, item-_min) return profit

주어진 배열에서 최소값들끼리 구해서 최대값을 만드는 문제 쉬움 난이도 문제이고, 문제만 보면 바로 이해가능함 Input: nums = [1,4,3,2] Output: 4 두 개씩 나올 수 있는 조합을 생각해보면 (1,4),(3,2) => 1+2 = 3 (1,3),(4,2) => 1+2 = 3 (1,2),(3,4) => 1+3 = 4 즉 정렬을 한 뒤에 답을 구하면 제일 큰 수를 알 수 있다. def arrayPairSum(self, nums: List[int]) -> int: nums.sort() sum = 0 for i in range(0, len(nums), 2): sum += min(nums[i], nums[i+1]) return sum 좀 더 빠르게 푸는 방법은 없을까? 책을 보니 거의 다 이렇게..

2월 1일 문제 십진수를 이진수로 변환했을때 1비트가 몇개 있느냐 검색하는 문제 난이도는 쉽다. def hammingWeight(self, n: int) -> int: count = 0 while n >0: if n & 1 == 1: count += 1 n>>=1 return count def hammingWeight(self, n: int) -> int: count = 0 print(n) while n >0: count += n%2 n//= 2 return count

예전에 풀었던 2Sum에 이은 3Sum문제.. a + b + c = 0이 되는 조합을 출력하는 것이고, 중복 조합은 허락하지 않는다. 중복을 허락하지 않으므로, set으로 결과 관리를 하면 될것 같음 n^3으로 풀릴것도 같다. 1) 첫번째 도전 (for문 3번) def threeSum(self, nums: List[int]) -> List[List[int]]: ans = [] nums.sort() check = set() for i in range(len(nums)): for j in range(i+1, len(nums)): for k in range(j+1, len(nums)): a, b, c, = nums[i], nums[j], nums[k] if a+b+c == 0 and (a,b,c) not in..

이 문제 어렵다. 고민하다가 책의 풀이를 봤다. 투 포인터를 이용해서 푸는데, 직접 손으로 그려봐야지 이해 가능했다. 설명은 좀 더 이따가...

배열과 특정 값이 주어지고, 배열 안에서 두 수를 합쳐 특정 값이 나올 수 있는지 찾는 문제 * 반드시 유의미한 정답은 한개는 있다 예를 들어서, [1,3,5,7,9]와 6이 주어지면 [1,5]로 6을 만들수 있고, 이것들의 위치를 넘겨주면 되는 문제 for 두 번 돌려서 확인 가능하다. def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(0, len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i, j] 근데 for 두번이면 시간 복잡도가 n^2이므로 이것보다 빠르게 하는 방법을 찾아보면... 1) in을 이용한다. -> ..

주어진 수를 2진수로 변환하면서 나오는 값들을 하나로 합쳐 다시 그 값을 10진수로 변환하는 문제 예를 들어, 3이면 아래 표와 같이 11101이 나오게 된다(1부터 3까지의 2진수를 하나로 합치는 것) 10진수 2진수 1 1 2 10 3 11 11101을 다시 10진수로 변환하면 27이 나온다. 파이썬에서 진법 문제를 다룰수 있는지를 보는 문제같다. 풀고나서 Discuss를 보니 신기한 방법으로 푼 애들도 있었다. def concatenatedBinary(self, n: int) -> int: s = "" for i in range(1, n+1): s += format(i, 'b') s = '0b'+ s return int(s, 2) % (10 ** 9 + 7) 참고로 진버과 관련해서는 아래 블로그를 ..

리스트를 오름차순으로 정렬하는 문제 다만 리스트 안에 관계가 linked-list로 이루어져있다. 더보기 Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6 아이디어 1) 기존 linked-list에서 새로운 linked-list를 만드는 방법 어차피 linked-list의 순서가 의미가 없으므로, value만 가져와 정렬후, 정렬된 값으로 새로 Link-list를 만든다. * 2차원 배열인줄 알고 for문 두번 돌려서 할려고 했..