파이썬 알고리즘 인터뷰 - Day 3 #1

원종운·2020년 8월 28일

두 수의 합

리트코드 1번 문제 : https://leetcode.com/problems/two-sum/
덧셈하여 타켓을 만들 수 있는 배열의 두 숫자 인덱스를 반환하라.

입력 :
- nums = [2, 7, 11, 15]
- target = 9
출력 : [0, 1]
설명 : 타켓 9를 만들 수 있는 배열의 두 숫자는 2와 7, 인덱스는 0과 1

풀이 1) 브루트포싱

실행 시간 : 5, 284 ms
리스트를 순회하여 두 수를 더하는 모든 조합에 대하여 타켓이 될 수 있는지를 검사하는 방식

class Solution:
  def two_sum_target(self, nums: List[int], target: int) -> List[int]:
    for outer in range(len(nums) - 1): # 리스트 순회, 기준점 - (1)
      for inner in range(outer + 1, len(nums)): # 리스트 순회, 기준점 이후 - (2)
        if (nums[outer] + nums[inner] == target): # 두 수의 합이 타켓일 경우
          return [outer, inner] # 결과 반환


test_case: List[int] = [2, 7, 11, 15] # 테스트 케이스
target = 17 # 타켓

solution = Solution() 
result: List[int] = solution.two_sum_target(test_case, target) # 알고리즘 호출
print(result) # 결과 : [1, 2]

(1) len(nums)가 아닌 len(nums)-1로 한 이유는, 기준점과 그 기준점 이후의 수의 조합으로 타켓이 되는지를 검사하기 때문에, 기준점은 len(nums)-1까지만 순회하여도 충분
(2) range(outer, len(nums))가 아닌 range(outer + 1, len(nums))인 이유는, 기준점과 그 기준점 이후의 수의 조합으로 검사를 하기때문이다. 그렇게 검사하는 이유는, 기준점 이전의 수 조합으로 타켓이 가능하다면, 이전에 이미 검사가 끝났을 거기때문에, 이후로 하는 것이 합당하다.
시간복잡도 T(n) = n(n-3)/2 + 1 = O(n^2)

풀이 2) 차를 조회하기

실행 시간 : 864 ms
풀이 1처럼 무작정 타켓을 만들 수 있는 두 숫자를 찾는 것이 아니라, 숫자를 순차적으로 조회하되 그 수와 함께 타켓을 만들 수 있는 수, 타켓에서 뺀 수를 조회하는 것이 핵심

class Solution:
  def two_sum_target(self, nums: List[int], target: int) -> List[int]:
    for index, num in enumerate(nums): # 리스트 순회
      complement: int = target - num # 타켓과의 차 계산
      if complement in nums[index+1:]: # 차가 리스트에 존재하는지 검사 - (1)
        return [index, nums[index+1:].index(complement) + (index + 1)] # 결과 반환 - (2)


test_case: List[int] = [2, 7, 11, 15] # 테스트 케이스
target = 18 # 타켓

solution = Solution() 
result: List[int] = solution.two_sum_target(test_case, target) # 알고리즘 호출
print(result) # 결과 : [1, 2]

(1)에서 "in nums"가 아닌 "in nums[index+1:]"를 한 이유는 num이 있는 위치 index 포함 이전에 원하는 수가 있었다면, 애초에 그 수를 기준으로 더해서 target이 되는 수가 이미 발견되었을 것입니다. 왜냐하면 쌍으로 존재하기때문입니다. 따라서 불필요한 조회를 막기 위해서 "in nums[index+1:]"를 해주는 것입니다.
(2)에서 (index+1)을 해주는 이유는 nums[index+1:]를 통하여 새로운 리스트가 생성되고, 기존의 nums의 index+1부터의 원소가 새로운 리스트의 0번째부터 시작하기때문에 index+1를 더하여 보정하여 준 것입니다.

시간복잡도 T(n) = n(n-1)/2 = O(n^2)
브루트포싱 방법보다 실질적인 연산 수는 많지만 시간 복잡도는 동일하다. 하지만 파이썬 내부에 구현된 in 메소드덕분에 전자의 방법보다 더 빠른 속도를 보장한다.

풀이 3) dict 사용 (two pass)

실행 시간 : 48 ms

class Solution:
  def two_sum_target(self, nums: List[int], target: int) -> List[int]:
    dict_nums: dict = {} # key : num, value : index의 형태로 dict 생성
    for index, num in enumerate(nums): # 리스트 순회 - (1)
      dict_nums[num] = index # 리스트의 index를 value, 리스트의 element를 key로 저장

    for index, num in enumerate(nums): # 리스트 순회  - (1)
      if (target - num in dict_nums) and (dict_nums[target - num] != index): # 더하여 target이 되는 수가 있을 경우  - (2)
        return [index, dict_nums[target- num]] # 결과 반환


test_case: List[int] = [2, 7, 11, 15] # 테스트 케이스
target = 17 # 타켓

solution = Solution() 
result: List[int] = solution.two_sum_target(test_case, target) # 알고리즘 호출
print(result) # 결과 : [1, 2]

(2)처럼 dictionary의 key를 조회하는 "key in dict"는 (1)처럼 list의 element를 조회하는 "elem in list"과는 다르게 O(n)이 소요되는 것이 아니라 O(1)이 소요된다.
따라서 위 알고리즘의 시간 복잡도는 O(n)이다.

풀이 4) dict 사용 (one pass)

실행 시간 : 44 ms
풀이 3에서 dictionary의 삽입과 조회를 나눠서 하는 것을 합친 것이다.
- 삽입과 조회가 일어나는 것은 똑같으므로 성능상의 이점은 없으나 코드가 간결해진다.

class Solution:
  def two_sum_target(self, nums: List[int], target: int) -> List[int]:
    dict_nums: dict = {} # key : num, value : index의 형태로 dict 생성

    for index, num in enumerate(nums): # 리스트 순회 
      if target - num in dict_nums: # 더하여 target이 되는 수가 있을 경우
        return [index, dict_nums[target- num]] # 결과 반환
      dict_nums[num] = index # 딕셔너리 삽입

모든 수를 dictionary에 삽입하고 검색하는 것이 아니라, 검색하고 나서 없을 시 삽입하는 One-Pass 구조이다.
One-Pass로 가능한 이유는, 순서쌍 (a, b)를 찾을때 a를 기준으로 b를 찾아도 되지만, b를 기준으로 a를 찾아도 무방하기때문이다.
- num 기준으로 target - num에 해당하는 값이 아직 dictionary에 추가되어있지 않더라도,
- target - num이 nums에 있다면 결과적으로 num에 target - num이 될 때는 dictionary에 있을 것이기때문에 발견되는 시점만 다르다.

빗물 트래핑

리트코드 42번 문제 : https://leetcode.com/problems/trapping-rain-water
높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

입력 : height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
출력 : 6
설명 :

풀이 1) 유사 투 포인터

최대 블럭 높이 기준으로 좌우 구간으로 나누어, 물이 쌓일 수 있는 구간을 탐색하여 구한 후 합한다.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: # 빈 리스트일 경우
            return 0 # 0 반환

        volume: int = 0 # 쌓이는 물의 양
        max_height_index: int = height.index(max(height)) # 가장 높은 블럭의 높이
        left_height: List[int] = height[:max_height_index+1] # 가장 높은 블럭 기준 좌측
        right_height: List[int] = list(reversed(height[max_height_index:])) # 가장 높은 블럭 기준 우측

        left, right = 0, 1
        while right < len(left_height):
            if left_height[left] > left_height[right]: # 좌측 칸막이보다 높이가 낮은 경우
                volume += left_height[left] - left_height[right] 좌측 칸막이와의 높이차만큼 물을 쌓는다
                right += 1 # 칸막이 구간을 넓힌다
            else: # 좌측 칸막이 벽의 높이보다 같거나 큰 경우
                left, right = right, right + 1 # 다음 구간으로 넘어가기

        left, right = 0, 1
        while right < len(right_height):
            if right_height[left] > right_height[right]: # 좌측 칸막이보다 높이가 낮은 경우
                volume += right_height[left] - right_height[right] # 좌측 칸막이와의 높이차만큼 물을 쌓는다
                right += 1 # 칸막이 구간을 넓힌다
            else:
                left, right = right, right + 1 # 다음 구간으로 넘어가기
            
        return volume # 반환

test_case: List[int] = [0,1,0,2,1,0,1,3,2,1,2,1] # 테스트 케이스

solution = Solution()
result: int = solution.trap(test_case) # 알고리즘 호출
print(result) # 결과 : 6

원종운

Java, Python, JavaScript Lover

이전 포스트

파이썬 알고리즘 인터뷰 - Day 2 #2

다음 포스트

파이썬 알고리즘 인터뷰 - Day 3 #1

두 수의 합

풀이 1) 브루트포싱

풀이 2) 차를 조회하기

풀이 3) dict 사용 (two pass)

풀이 4) dict 사용 (one pass)

빗물 트래핑

풀이 1) 유사 투 포인터

파이썬 알고리즘 인터뷰 - Day 2 #2

파이썬 알고리즘 인터뷰 - Day 4 #1

0개의 댓글