leetcode 7

[연결 리스트] 팰린드롬 연결 리스트

* leetcode 234. Palindrome Linked List Q. 연결리스트가 팰린드롬 구조인지 판별하라. # 입력 1->2 # 출력 false # 입력 1->2->2->1 # 출력 true 풀이 1. 리스트 변환 # 연결 리스트를 파이썬의 리스트로 변환시켜 풀이 def isPalindrome(head: ListNode) -> bool: q: List = [] if not head: return True node = head # 리스트 변환 while node is not None: q.append(node.val) node = node.next # 판별 while len(q) > 1: if q.pop(0) != q.pop(): # 인덱스를 지정하여 처음과 끝 값을 비교 return False ..

[배열] 자신을 제외한 배열의 곱

* leetcode 238. Product of Array Except Self Q. 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라. # 입력 [1, 2, 3, 4] # 출력 [24, 12, 8, 6] # 나눗셈을 하지 않고 O(n)으로 풀이하라. 풀이 1. 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈 # 자신을 제외한 왼쪽 곱셈 결과 # [1, 1, 2, 6] # 자신을 제외한 오른쪽 곱셈 결과 # [24, 12, 4, 1] # 이 둘을 곱하면 # [ 1, 1, 2, 6] # [24, 12, 4, 1] # [24, 12, 8, 6] -> 답 def productExceptSelf(nums: List[int]) -> List[int]: out = [] ..

[배열] 배열 파티션 1

* leetcode 561. Array Partition 1 Q. n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라. # 입력 [1, 4, 3, 2] # 출력 [4] # 설명 n은 2가 되면, 최대 값은 4이다. min(1, 2) + min(3, 4) = 4 풀이 1. 오름차순 풀이 최대 min()을 만들기 위해서 내림차순으로 배열을 만들면 항상 최대 min() 페어를 만들 수 있다는 점을 활용한다. 이때, 문제에서 배열 입력값은 2n개일 것이기 때문에 오름차순으로도 같은 결과가 나온다. def arrayPairSum(nums: List[int]) -> int: sum = 0 pair = [] nums.sort() for n in nums: pair.append(n) ..

[배열] 새 수의 합

* leetcode 15. 3Sum Q. 배열을 입력받아 합으로 0을 만들 수 있는 3개의 앨리먼트를 출력하라 # 입력 nums = [-1, 0, 1, 2, -1, -4] # 출력 [ [-1, 0, 1], [-1, -1, 2] ] 풀이 1. 브루트 포스로 계산 # 3개의 포인터를 이용하여 모두 더해서 0이 되는 값들을 찾는다. def threeSum(nums: List[int]) -> List[List[int]]: results = [] nums.sort() # n^3 반복 for i in range(len(nums) - 2): # 중복값 제거 if i > 0 and nums[i] == nums[i - 1]: continue for j in range(i + 1, len(nums) - 1): if j >..

[Leetcode] Container With Most Water

solution for Container With Most Water Problem) Solution) 2개의 포인터를 활용해서 시간 복잡도 O(n)에 끝낼 수 있다. max_water 변수에는 각 단계별 최대 물의 양을 저장한다. x, y 포인터 초기화하고 각각 x는 시작점, y는 끝점에 위치하고 하나씩 옮기며 최대 물의 양을 계산하고 max_water의 값과 비교하여 최종 최대 물의 양 값을 얻는다. 이때 포인터를 옮기는 과정에서 x, y 포인터가 가르키는 막대의 길이를 비교하여 길이가 짧은 막대의 포인터를 x는 +1, y는 -1로 한칸씩 옮겨야 한다. Example의 예를 들면 최초 x는 0 (height[0] = 1)을 가르키고 y는 8 (height[8] = 7)을 가르킨다. 여기서 물의 양을 ..

알고리즘 2020.06.04