leetcode

3부 선형구조

07. 두 수의 합

• 1. Two Sum
• https://leetcode.com/problems/two-sum/

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.

• 입력 nums[0] + nums[1] = 2 + 7 = 9

• 출력 [0, 1]

• 설명 nums[0] + nums[1] = 2 + 7 = 9 따라서 0, 1을 리턴한다.

풀이01. 브루트포스로 계산

def solution(N, stages):
  # 스테이지별 도전자 수를 구함
  challenger = [0] * (N + 2)
  for stage in stages:
    challenger[stage] += 1

  # 스테이지별 실패한 사용자 수 계산
  fails = {}
  total = len(stages)

  # 각 스테이지를 순회하며, 실패율 계산
  for i in range(1, N + 1):
    if challenger[i] == 0: # 도전한 사람이 없는 경우, 실패율은 0
      fails[i] = 0
    else:
      fails[i] = challenger[i] / total # 실패율 구함
      total -= challenger[i] # 다음 스테이지 실패율을 구하기 위해 현재 스테이지의 인원을 뺌

  # 실패율이 높은 스테이지부터 내림차순으로 정렬
  result = sorted(fails, key=lambda x : fails[x], reverse=True)
  
  return result

풀이02. in을 이용한 탐색

def twoSum(self, nums: List[int], target: int) -> List[int]:
  for i, n in enumerate(nums):
    complement = target - n

    if complement in nums[i + 1]:
      return [nums.index(n), nums[i + 1:].index(complement) + (i + 1)]

풀이03. 첫번째 수를 뺀 결과 키 조회

def twoSum(self, nums: List[int], target: int) -> List[int]:
  nums_map = {}
  # 키와 값을 바꿔서 딕셔너리로 저장
  for i, num in enumerate(nums):
    nums_map[num] = i

  # 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
  for i, num in enumerate(nums):
    if target - num in nums_map and i != nums_map[target - num]:
      return [i, nums_map[target - num]]