[Python] 미국 회사 코딩 테스트 예제: Solve the Two-Sum Problem Using a Hash Map
포스트 난이도: HOO_Middle
# Problem Statement
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
- Example: Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1]
- Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
- Solution: To solve this problem efficiently, we can utilize a hash map to store the difference between the target and each element as we iterate through the array. This approach allows us to achieve a linear time complexity.
# Hashmap and Time Complexity
개발쟁이들의 습관이라고 할 수 있듯이 문제가 있으면 가장 먼저 봐야 하는 것이 "무엇을 원하는지"이다. 문제 내용이 길게 서술되어 있다면 본질적으로 "무엇을" 원하는지만 파악하면 그다음부터는 걱정이 없다.
위의 문제의 내용을 한마디로 요약하자면 Hashmap과 Time complexity에 대해서 알고 있는지를 물어보고 있다. 내가 느낀 과제가 아닌 코딩 테스트의 경우 개념을 제대로 파악하고 있는지를 보려고 하기 때문에 생각보다 물어보는 질문이나 문제 자체가 어렵지는 않다. 따라서 핵심만 파악한다면 그다음부터는 긴장할 필요가 없다는 것이다.
본론으로 돌아와서 Hashmap을 사용을 하면 된다고 파악 되었으니, 프레임 코드를 만들면 된다. 프레임 코드는 그림으로 치면 스케치에 해당한다. 마구 틀려도 좋으니 일단 기본 틀을 설계하는 단계라고 생각하면 된다.
하나의 팁은 코드 자체에 comments (주석)를 작성해 두는 것이다. 코멘트를 작성할 때 핵심 요지 또는 키워드정도로 정리해 두는 것이 좋다.
"저는 코멘트를 작성하지 않아도 문제를 기억할 수 있는데요"라고 한다며 코멘트를 별도로 작성해두지 않아도 된다. 내가 코멘트를 정리해 두는 또다른 이유는 코딩 테스트가 정답 유무 뿐만 아니라 코드 작성에 대한 스타일도 평가될 수 있기 때문이다.
한마디로 정답과 풀이과정 모두가 중요하다는 것이다. 나의 경우 깔끔한 (가독성이 좋은) 코드 작성 여부도 보기 때문에 테스트이지만 다른 개발자와 코드를 공유한다는 마음으로 작성하는 편이다. 물론 "한국은 사람이 평가를 일일이 하지 않는데요"라고 할 수 있지만 내가 심사를 할 경우에는 코드 자체가 깔끔하고 가독성이 좋은지도 보는 편이다.
def two_sum(nums, target):
"""
Finds two indices in the list nums such that their corresponding values add up to the target.
Args:
nums (list of int): The list of integers to search through.
target (int): The target sum to find.
Returns:
list of int: A list containing the indices of the two numbers that add up to the target.
"""
num_to_index = {}
for index, num in enumerate(nums):
complement = target - num
if complement in num_to_index:
return [num_to_index[complement], index]
num_to_index[num] = index
return []# Results
프레임 코드 작성이 끝났으면 실제로 Example에 나와 있는 값들을 입력해서 테스트를 해본다. 최종 제출해야 될 코드의 경우 Example values들이 포함되어 있는 코드를 제출하는 편이다. 물론 별도의 Exmple이 제시되어 있지 않거나 프레임 코드만 제출해도 문제는 없다.
def two_sum(nums, target):
"""
Finds two indices in the list nums such that their corresponding values add up to the target.
Args:
nums (list of int): The list of integers to search through.
target (int): The target sum to find.
Returns:
list of int: A list containing the indices of the two numbers that add up to the target.
"""
num_to_index = {} # Dictionary to store number and its index
for index, num in enumerate(nums):
complement = target - num
if complement in num_to_index:
return [num_to_index[complement], index]
num_to_index[num] = index
return []
# Example usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))