멋진 개발자가 되고 싶다

한 번의 거래로 낼 수 있는 최대 이익을 산출하라. Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell. 1. 내가 직접 푼 코드 1 2 3 4 5 6 7 class Solution: def maxProfit(self, prices: List[int]) -> int: max_profit = [] for i in range(len(prices)-1): max_..

배열을 입력받아 Output [i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라. Input: nums = [1,2,3,4] Output: [24,12,8,6] *단, 나눗셈을 하지 않고 O(n)에 풀이하라. 사실 좀 어려워서 고민하다가 풀이 제목을 봤다. 보통 저 문제를 풀면 바로 떠오르는 것은 for문을 중복하여 곱해 나간다던지 전체를 곱하고 요소에서 나눠준 값을 넣는다던지가 있는데 전자는 시간 복잡도가 O(n^2)이 돼버리기에 안되고 후자는 문제 주인장이 그렇게 쉽게 풀지 말래서 안된다. ㅋ~ 1. 내가 직접 푼 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 left = [] right ..

n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라. Input: nums = [1,4,3,2] Output: 4 Explanation: All possible pairings (ignoring the ordering of elements) are: 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 So the maximum possible sum is 4. 1. 내가 직접 푼 코드 1 2 3 4 5 6 7 8 class Solu..

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라. Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2], [-1,0,1]] 1. 내가 직접 푼 코드 1 2 3 4 5 6 7 8 9 10 11 class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums_list = [] for i in range(len(nums) - 2): for j in range(i + 1, len(nums) - 1): for k in range(j + 1, len(nums)): if nums[i] + nums[j] + nums[k] == 0 : v = sorted([nums[i], nums[j], n..

높이를 입력받아 비 온 후 어마나 많은 물이 쌓일 수 있는지 계산하라. 1. 내가 직접 푼 코드 ... 해설: 너무 어려워서 풀다 포기함.. ** 깔끔한 답안 ** 2. 투 포인터를 최대로 이동 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def trap(self, height: List[int]) -> int: if not height: return 0 volume = 0 left, right = 0, len(height)-1 left_max, right_max = height[left], height[right] while left

덧셈하여 타깃을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. 단, 정답은 하나이다. 1. 내가 직접 푼 코드 1 2 3 4 5 6 7 class Solution: def twoSum(nums: list, target: int) -> list: # 브루트 포스로 계산 for i in range(len(nums)-1): for j in range(i+1,len(nums)): if nums[i] + nums[j] == target: return [i,j] cs 해설 : 단순 반복으로 풀었다. 반복문 두개로 진행하다 보면 target 값을 구할 수 있다. 단, 시간이 너무 많이 든다. RunTime : 4012ms ** 여러가지 답안 ** 2. in을 이용한 탐색 1 2 3 4 5 6 7 class Sol..

가장 긴 팰린드롬 부분 문자열을 출력하라 Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer. 내가 직접 푼 코드 ,,, 해설 : 아쉽게도 없다... 나는 이 문제를 풀지 못했기 때문이다. 우선 나는 처음에 홀수 팰린드롬만 생각하고 코드를 짰다. 하지만 아쉽게도 팰린드롬은 bb와 같이 짝수인 경우도 있다. 그리고 무엇보다 s [::-1]을 응용하여 역순과 정순을 비교하여 팰린드롬을 찾으려 했지만 초반부에 s[0:-1:-1]이 계산이 안돼서 깔끔하게 만들지 못할 것 같아 3시간 고민하고 gg... ** 깔끔한 답안 ** 1. 중앙을 중심으로 확장하는 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 c..

문자열 배열을 받아 애너그램 단위로 그룹핑하라. 어떤 순서로든 답을 반환해도 된다. 1. 내가 직접 푼 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: strs.sort(key=lambda x: sorted(x)) # 정렬된 str을 기준으로 줄 세우기 output = list() output.append([strs[0]]) strs.pop(0) i = 0 # 앞의 str과 비교하여 애너그램이면 앞 str의 리스트에 추가, 그렇지 않으면 따로 리스트 생성 for str in strs: if sorted(str) == sorted(output[i][..