코딩 테스트 자주 나오는 문제: 두 수의 합 (Two Sum)

코딩 테스트 단골손님: 두 수의 합 (Two Sum)

면접관이 좋아하는 문제 Top 3 안에 반드시 들어가는 두 수의 합!(근거 없음.)

심지어 파이썬, 자바스크립트, 자바, C++ 가리지 않고 나오는 무적의 인기 문제다. 이걸 몰라? 그럼 면접관이 속으로 "이 친구는 기본기가 부족하구만..." 할지도 모른다 🤔 (이 또한 근거없음.)

 

 

문제 설명

정수 배열 nums와 정수 target이 주어졌을 때, 배열에서 두 수의 합이 target이 되는 인덱스를 찾아 반환하시오.
단, 딱 한 쌍만 존재한다는 전제가 있다 (즉, 여러 쌍 없음!).

 

입력 예시

nums = [2, 7, 11, 15], target = 9
// 출력: [0, 1] (2 + 7 = 9)

 

 

 

1. 순수 근성 풀이: 이중 for문

음...... 그냥 for 두 개 돌려서 다 더해보자!

물론 맞긴 한다. 다만 면접 끝나고 "왜 최적화 안 했는지" 물어볼 수도 있음 😅

function twoSum(nums, target) {
  let arr = [];

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

  return arr;
}

• 장점: 무지성으로라도 풀 수 있음
• 단점: 시간 복잡도 O(n²) → 배열 길어지면 컴퓨터가 숨 참음

 

 

2. 머리 좀 쓴 풀이 : 해시맵으로 최적화!

자, 이제 진짜 개발자처럼 풀어보자.
한 번만 순회하면서 필요한 수가 이미 등장했는지 저장해두면? O(n)으로 해결 가능! "아 이게 그 유명한 해시맵(hashMap) 풀이구나!" 하고 면접관 눈이 반짝일지도✨(안 반짝일지도..쩝)

function twoSum(nums, target) {
  const map = {};

  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    const complement = target - num;

    if (Object.prototype.hasOwnProperty.call(map, complement))) {
      return [map[complement], i];
    }

    map[num] = i;
  }

  return [];
}

• 장점: O(n) 시간 복잡도
• 단점: hasOwnProperty()를 사용해야 하는데, 조금 더 복잡할 수 있음

 

 

잠깐, 자바스크립트에 해시맵이 있어?

엄밀히 말해 HashMap은 없어. 하지만 {} 또는 new Map()을 쓰면 그게 바로 우리가 말하는 "해시맵"!

const map = {};
map['🍕'] = '피자';
console.log(map['🍕']); // 피자
console.log(map.hasOwnProperty('🍕')); // true

그럼 키에 이모지 써도 되냐고?
돼. 하지만 그러지 말자 😇

 

 

3. Map 객체로 더 깔끔하게 리팩토링

그럼, 이제 Map을 사용해서 더 직관적이고 깔끔한 코드로 바꿔보자! Map은 내부적으로 더 최적화된 자료구조로, 더 안전하고 효율적인 방식으로 데이터를 관리할 수 있음.

function twoSum(nums, target) {
  const map = new Map();

  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    const complement = target - num;

    if (map.has(complement)) {
      return [map.get(complement), i];
    }

    map.set(num, i);
  }

  return [];
}

• 장점: has와 get 메서드를 사용해 객체처럼 키-값을 빠르게 다룰 수 있음
• 단점: 사실상 단점이라고 할 건 없지만, Map 객체를 지원하지 않는 구형 브라우저나 환경에서는 사용할 수 없을 수도 있음

 

 

보너스: 문자열 순회할 때 꼭 배열로 바꿔야 할까?

아니다! for...of는 문자열도 바로 순회 가능하다. 몰랐다면 이 기회에 손에 붙이자!

for (const char of "banana") {
  console.log(char); // 'b', 'a', 'n', ...
}

문자 카운트도 이렇게 깔끔하게 쓸 수 있음:

const countMap = {};
for (const char of str) {
  countMap[char] = (countMap[char] || 0) + 1;
}

 

 

 

마무리 정리

• "두 수의 합"은 진짜 잘 나오고
• 브루트포스 vs 해시맵 풀이 비교로 문제 해결 방식도 보여주고
• 심지어 객체 활용법까지 자연스럽게 익힐 수 있는

 

그야말로 면접 단골이자 실무 감성 문제. 한 번 확실히 익혀두면 다른 배열 문제도 수월하게 풀 수 있다!

다음 글은 "세 수의 합"? (미래의 내가 욕하는 소리가 들린다...)