HTTP:! HTTP:!

주어진 linked list가 순환하는지 판별하는 문제이다. 이전에 234번에서 풀었던 Runner 기법을 이용하면 쉽게 풀린다. hongprogrammer.tistory.com/entry/234-Palindrome-Linked-List 234. Palindrome Linked List 주어진 linked list가 회문인지 판단하는 문제이다. 난이도는 쉽다. linked list를 직접 변경할 수 없으니, in-out이 쉬운 구조가 되어야한다. python에서는 list에서 특정 지점에서 pop도 지원한다. 1) list 이 hongprogrammer.tistory.com slow는 한칸씩 가면서, fast는 두칸씩 전진해서 나간다. 무한 반복해가면서 같은것이 나올때까지 돌린다. def hasCycle..

주어진 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을 이용한다. -> ..