[알고리즘]Leetcode-배열

두 수의 합(Two Sum)

• 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라
• 입력
  nums = [2, 7, 11, 15], target = 9
• 출력
  [0, 1]
• 풀이 : 첫번째 수를 뺀 결과 키 조회

  class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
          
        for i, num in enumerate(nums):
            # 2) 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
            if target - num in nums_map:
                return [nums_map[target - num], i]
            # 1) 키와 값을 바꿔서 딕셔너리로 저장
            nums_map[num] = i
  

빗물 트래핑(Trapping Rain Water)

• 높이를 입력 받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.
• 입력
  [0,1,0,2,1,0,1,3,2,1,2,1]
• 출력
  6
• 풀이 1) 투 포인터 이동 (64ms)

  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 < right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)
              
            # 더 높은 쪽을 향해 투 포인터 이동
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
          
        return volume
  

• 풀이 2) 스택 (43ms)

  class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        volume = 0
          
        for i in range(len(height)):
            # 변곡점(현재높이가 이전 높이보다 높을때) 만나는 경우
            while stack and height[i] > height[stack[-1]]:
                # 스택에서 꺼냄
                top = stack.pop()
                  
                if not len(stack):
                    break;
                  
                # 이전과의 차이만큼 물 높이 처리 
                distance = i - stack[-1] - 1 
                waters = min(height[i], height[stack[-1]]) - height[top]
                volume += distance * waters
              
            stack.append(i)
        return volume
  

세 수의 합 (3Sum)

• 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라
• 입력
  nums = [-1, 0, 1, 2, -1, -4]
• 출력

    [-1, 0, 1],
    [-1, -1, 2]
  ]
  

• 풀이 : 투 포인터

  class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        results = []
        nums.sort()
          
        for i in range(len(nums) - 2):
            # 중복된 값 건너뛰기 
            if i > 0 and nums[i] == nums[i - 1]:
                continue
              
            # 간격을 좁혀가며 합 sum 계산
            left, right = i+1, len(nums) - 1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                else:
                    results.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
          
        return results
  

배열 파티션 I (Array Partition I)

• n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라
• 입력
  [1,4,3,2]
• 출력
  4
• 설명
  n은 2가 되며, 최대 합은 4이다. min(1,2) + min(3, 4) = 4
• 풀이 : 오름차순 짝수번째 계산하기

  class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2]) # 두칸씩 건너뛰어 짝수 보기 
  

자신을 제외한 배열의 곱 (Product of Array Except Self)

• 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라
• 입력
  [1,2,3,4]
• 출력
  [24,12,8,6]
• 주의 : 나눗셈을 하지 않고 O(n)에 풀이하라
• 풀이 : 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈

  class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        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
  

주식을 사고팔기 가장 좋은 시점 (Best Time to Buy and Sell Stock)

• 한 번의 거래로 낼 수 있는 최대 이익을 산출하라
• 입력
  [7,1,5,3,6,4]
• 출력
  5
• 설명 : 1일때 사서 6일때 팔면 5의 이익을 얻는다.
• 풀이 : 저점과 현재 값과의 차이 계산
  • 현재값을 가리키는 포인터가 우측으로 이동하면서 이전의 저점을 기준으로 가격 차이 계산 후, 클 경우 최댓값을 계속 교체
  • idea) 최댓값은 최솟값으로, 최솟값은 최댓값으로 지정 => 교체될 수 있도록

     class Solution:
      def maxProfit(self, prices: List[int]) -> int:
      profit = 0 
      min_price = sys.maxsize
            
      # min과 max를 계속 갱신
      for price in prices:
          min_price = min(min_price, price)
          profit = max(profit, price - min_price)
            
      return profit