문제를 푸는 기준

모든 쌍을 직접 비교하기 전에 이미 본 값을 Set이나 Map에 기록해 한 번의 순회로 바꿀 수 있는지 확인합니다.

핵심 개념

대표 문제

서로 다른 값 쌍 세기

정수 배열 numbers와 target이 주어집니다. 합이 target인 서로 다른 값 쌍의 개수를 반환하세요. 같은 값 쌍은 여러 번 등장해도 한 번만 셉니다.

함수 시그니처: solution(numbers, target)

제한사항

• numbers의 길이는 1 이상 200,000 이하입니다.
• 같은 값이 여러 번 등장할 수 있습니다.
• 한 원소를 자기 자신과 두 번 사용할 수 없습니다.

입출력 예

풀이 설계

1. seen에 앞에서 본 값을 기록합니다.
2. 현재 값마다 target과의 차이를 찾습니다.
3. 발견한 쌍은 작은 값과 큰 값으로 정규화해 pairs에 넣습니다.

JavaScript 풀이

function solution(numbers, target) {
  const seen = new Set();
  const pairs = new Set();
  for (const value of numbers) {
    const complement = target - value;
    if (seen.has(complement)) {
      const left = Math.min(value, complement);
      const right = Math.max(value, complement);
      pairs.add(left + ':' + right);
    }
    seen.add(value);
  }
  return pairs.size;
}

복잡도

• 시간복잡도: O(n)
• 공간복잡도: O(n)
• 핵심 패턴: 이미 본 값을 Set에 기록해 이중 반복 제거
• 경계 사례: 같은 수 쌍은 그 값이 실제 두 번 등장해야 인정

연습 문제

1. 중복 존재

같은 값이 두 번 이상 있으면 true를 반환하세요.

2. 첫 중복 위치

처음 두 번째로 등장한 값의 인덱스를 반환하세요.

3. 세 수의 합

세 인덱스의 합이 target인 조합 수를 구하세요.

자주 하는 실수

• 작은 예시만 보고 O(n²)을 선택하는 실수
• 평균 O(1) 조회와 전체 O(n)을 혼동하는 실수
• 값 쌍과 인덱스 쌍을 혼동하는 실수
• 추가 메모리를 분석에서 빼는 실수

핵심 정리

• 함수 시그니처와 반환 자료형을 먼저 확정합니다.
• 제한사항으로 가능한 시간복잡도를 판단합니다.
• 예시와 경계 사례를 손으로 추적한 뒤 구현합니다.
• 완성한 solution 함수가 입력을 불필요하게 바꾸지 않는지도 확인합니다.

확인 문제

참고 자료

• MIT OpenCourseWare 6.006 Introduction to Algorithms 
• MIT 6.006 알고리즘 설명·정당성·복잡도 지침 
• MDN Set