HTTP:! HTTP:!

주어진 linked list가 회문인지 판단하는 문제이다. 난이도는 쉽다. linked list를 직접 변경할 수 없으니, in-out이 쉬운 구조가 되어야한다. python에서는 list에서 특정 지점에서 pop도 지원한다. 1) list 이용하는 방법 def isPalindrome(self, head: ListNode) -> bool: lst = [] if not head: return True while head: lst.append(head.val) head = head.next while len(lst)>1: if lst.pop(0) != lst.pop(): return False return True 위 방법은 pop할때마다 list를 재배치하기때문에 시간이 더 많이 들 수 밖에 없다. 그리고..

특정 시점에 주식을 사서 최대 이익을 보면서 파는 문제 사실 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) 참고로 진버과 관련해서는 아래 블로그를 ..