Two Sum 문제

Source: Dev.to

안녕하세요! 오늘은 Two Sum 문제를 푸는 방법을 설명하려고 합니다. 대부분의 개발자라면 코딩을 처음 연습하거나 면접을 준비할 때 이 문제를 한 번쯤은 본 적이 있을 겁니다.

아직 이 문제를 풀어본 적이 없는 소프트웨어 업계 종사자들을 위해, 단계별로 접근 방법을 보여드리겠습니다.

시작해볼까요.

Question

정수 배열 nums와 정수 target이 주어졌을 때, 두 수의 인덱스를 반환하세요. 두 수의 합이 target이 되어야 합니다.

각 입력에는 정확히 하나의 해답이 존재한다고 가정하며, 같은 요소를 두 번 사용할 수 없습니다.

답은 어떤 순서로든 반환해도 됩니다.

Example

Input: nums = [2,11,15,7], target = 9
Output: [0,3]
Explanation: Because nums[0] + nums[3] == 9, we return [0, 3].

Solution

function twoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

const nums = [2, 11, 15, 7];
const target = 9;

console.log(twoSum(nums, target)); // Answer: [0, 3]

Explain the solution

• nums와 target 두 매개변수를 받는 함수를 만든다.
• 배열에서 합이 target이 되는 두 숫자를 찾기 위해 두 개의 반복문을 사용한다:
  • 외부 루프는 배열의 각 요소를 순회한다.
  • 내부 루프는 현재 외부 루프 인덱스 이후의 요소들을 검사한다.
• 예를 들어 [2, 11, 15, 7]인 경우:
  • 외부 루프가 2에 있을 때, 내부 루프는 11, 15, 7을 확인한다.
• 내부 루프에서 두 숫자의 합이 target과 같은지 확인한다.
• 같다면 해당 인덱스를 반환한다.
• 모든 경우를 확인했는데도 짝이 없으면 빈 배열을 반환한다.
• 끝!

Performance consideration

이 솔루션은 이해하기 쉽고 정상적으로 동작하지만 효율적이지는 않다. 모든 가능한 쌍을 검사하기 때문에 시간 복잡도는 **O(n²)**이다.

다음 글에서는 시간 복잡도를 낮춘 더 효율적인 풀이를 소개할 것이다—이는 면접과 실제 프로젝트 모두에 유용할 것이다.

읽어 주셔서 감사하고, 계속해서 학습하세요!

Reference

https://leetcode.com/problems/two-sum/description/