1. Two Sum – 엔지니어 대한민국

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

문제

정수가 담긴 하나의 배열이 있습니다. 그리고 두개의 정수를 합한 어떤 정수 하나가 주어졌어요. 주어진 정수는 배열 안의 숫자 두개를 더해서 나온 값이에요. 배열안에 오직 하나의 정답이 존재하고, 배열방의 값은 단 한번만 사용할수 있다고 가정할때, 어떤 방의 값들이 더해져서 주어진 정수가 나온건지 해당하는 배열방의 번호를 두개 반환하시오.

풀이

일단 문제가 나오면 서두르지 말고, 생각을 정리하세요. 문제를 정확하게 이해해야 풀이도 가능한거랍니다. 그리고 생각이 정리되면 수도코드로 코드를 대충 짜보세요. 이때는 코드의 정확성은 중요하지 않고, 알고리즘이 옳은 방향인지를 가늠해보는 단계이기 때문에 에러가 날것등은 신경쓰지 않고 일단 생각을 자유롭게 펼쳐봅니다.

그런데 오히려 맨땅에 헤딩하는 것보다 기본 템플릿을 깔아 놓고 시작하면 면접장에서 좀더 마음이 편안하고 막연할때 뭐라도 코드를 떼서 불안한 마음을 정돈하고 코딩에 집중할수 있는 바탕을 깔아놓습니다.

def main():

if __name__ == '__main__':
    main()

그뒤로 본격적인 코딩에 앞서 가장먼저 생각 해야할것은 클래스나 함수의 구조입니다. 큰 틀을 우선적으로 잡아놓고 그 안에서 디테일을 하나씩 쳐나가는 거죠. 이 문제의 경우는 검색할 배열과 주어진 정수를 인자로 받는 함수를 하나 선언합니다. 아직 안에 어떤 로직을 넣어야할지는 모르겠지만 우선 그런 함수를 만들겠다는 생각을 하고 있다는걸 보여주는거죠. 그리고 예제로 사용할 배열방과 정수값을 임의로 하나 만듭니다. 막연히 함수를 만드는것보다 예제값을 머리속에 대입해보면서 코딩을 하면 좀더 구체적으로 로직을 떠올릴수 있거든요.

def twoSum(nums, target):

def main():
  nums = [2, 7, 11, 15]
  target = 9
  twoSum(nums, target)

if __name__ == '__main__':
  main()

그럼 이제 본격적으로 알고리즘을 만들어 볼게요. 일단 무식하게 풀어보면 배열방을 돌면서 하나씩 다 더해보면 되지 않을까요? 주어진 배열과 정수를 변수에 담고, for문을 돌면서 확인합니다. 저는 간단하게 이렇게 시작해봤어요. 두개의 배열을 교차로 돌다가 더해보고 값이 나오면 출력한뒤 빠져나오는 거죠.

def twoSum(nums, target):
  for num1 as nums:
    for num2 as nums:
      if num1 + num2 == target:
        print(f'num1: {num1}, num2: {num2}')
        return

def main():
  nums = [2, 7, 11, 15]
  target = 9
  twoSum(nums, target)

if __name__ == '__main__':
    main()

그런데 문제에 배열방의 번호를 넘기라고 했으니까 for문을

다른 결과들

def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            mid = target - nums[i]
            for j in range(i+1,len(nums)):
                if nums[j] == mid:
                    return [i,j]

class Solution:
    def twoSum(self, nums, target):
        num_set = {}
        for num_index, num in enumerate(nums):
            if (target-num) in num_set:
                return [num_set[target-num], num_index]
            num_set[num] = num_index

def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
    """
    finds two numbers which add to a given target number and returns their indices
    """
    # create dict to store reciprocal digits
    r = {}
    # loop through nums (keep index)
    for x in range(0, len(nums)):
        n = target - nums[x]
        # check dict for reciprocal of current number
        if n in r:
            return [r[n], x]
        # if not in dict, add current number to avoid doubles
        r[nums[x]] = x

문제

풀이

다른 결과들

참고자료