주식을 사고팔기 가장 좋은 시점 한번의 거래로 낼 수 있는 최대 이익을 산출하라. 입력 [7,1,5,3,6,4] 출력 5 1일 때 사서 6일 때 팔면 5의 이익을 얻는다. # 풀이 1. 브루트 포스로 계산 def maxProfit(prices): max_price = 0 for i , price in enumerate(prices): for j in range(i,len(prices)): max_price = max(prices[j]-price, max_price) return max_price prices = [7,1,5,3,6,4] maxProfit(prices) >>> 5 import sys # 풀이 2. 저점과 현재 값과의 차이 계싼 def maxProfit(prices): profit = 0 m..

자신을 제외한 배열의 곱 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라. 입력 [1,2,3,4] 출력 [24,12,8,6] 주의 나눗셈을 하지 않고 O(n)에 풀이하라. def productExcpetSelf(nums): out = [] p = 1 # 왼쪽 곱셈 for i in range(0, len(nums)): out.append(p) p = p * nums[i] p = 1 # 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈 for i in range(len(nums)-1, 0 -1, -1): out[i] = out[i] * p p = p * nums[i] return out productExceptSelf(nums) >>> [24, 12, 8, 6]

n개의 pair를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력하라. 입력 [1,4,3,2] 출력 4 설명 n은 2가 되며, 최대 합은 4이다 min(1,2) + min(3,4) = 4 # 풀이 1. 오름차순 풀이 def arrayPairSum(nums): sum = 0 pair = [] nums.sort() for n in nums: # 앞에서부터 오름차순으로 페어를 만들어서 합 계산 pair.append(n) if len(pair) == 2: sum+= min(pair) pair = [] return sum nums = [1,4,3,2] arrayPairSum(nums) >>> 4 # 풀이 2. 짝수 번째 값 계산 def arrayPairSum(nums): sum = 0 nums...

세수의 합 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라. 입력 nums = [-1, 0, 1, 2, -1, -4] 출력 [ [-1,0,1], [-1,-1,2] ] # 풀이1. 브루트 포스로 계산 def threeSum(nums): result = [] 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 > i+1 and nums[j] == nums[j-1]: continue for k in range(j+1,len(nums)): if k > j+1 and num..

빗물 트래핑 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 입력 [0,1,0,2,1,0,1,3,2,1,2,1] 출력 6 # 풀이 1. 투 포인터로 풀이 def trap(height): if not height: return 0 # 초기값 설정 volume = 0 left, right = 0, len(height)-1 left_max, right_max = height[left], height[right] while left > 6 # 풀이2. stack을 쌓..

7. 두수의 합 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라 입력 nums = [2,7,11,15], target = 9 출력 [0,1] # 풀이 1. 브루트 포스로 계산 def twosum(nums, target): for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i,j] twosum([2,7,11,15],9) >>> [0, 1] # 풀이 2. in을 이용한 탐색 def twosum(nums, target): for i , n in enumerate(nums): complement = target - n if complement in nums[i+1:]: ..