제목

Daily JavaScript Challenge #JS-181: Find the Smallest Missing Positive Integer

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

웹 개발

대상자

JavaScript 개발자 및 알고리즘 문제 풀이 초보자

난이도: 중간 (배열 조작 및 공간 복잡도 최적화 이해 필요)

핵심 요약

• 문제 정의: 주어진 배열에서 가장 작은 양의 정수 중 누락된 값을 찾는 문제 (예: [3,4,-1,1] → 2)
• 핵심 알고리즘:

- In-place 배열 조작 (O(1) 공간 복잡도)

- 배열의 인덱스와 값의 관계를 활용한 스왑 알고리즘

• 시간 복잡도: O(n)

섹션별 세부 요약

1. 문제 정의 및 예시

• 배열에 포함된 양의 정수만 고려
• 0 또는 음수는 무시
• 예: [1,2,3] → 4, [2,3,4] → 1

2. 일반적인 접근법

• 해시 집합 사용:

- 배열을 순회하며 양의 정수를 집합에 저장

- 1부터 시작해 집합에 없는 첫 번째 정수를 반환 (공간 복잡도 O(n))

• 배열 정렬 후 순회:

- 배열을 정렬 후 1부터 시작해 누락된 정수를 찾음 (시간 복잡도 O(n log n))

3. 최적화된 알고리즘 (In-place)

• 배열의 인덱스와 값의 관계를 활용:

- 배열의 각 요소가 1 ≤ x ≤ n 범위에 있을 때, 해당 값을 인덱스 x-1에 배치

- 이 과정에서 스왑을 반복하여 배열을 재정렬

• 최종 배열 순회 후, 인덱스 +1이 누락된 값

4. 구현 예시 (JavaScript)

function firstMissingPositive(nums) {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] !== nums[i]) {
      [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
    }
  }
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return nums.length + 1;
}

결론

• In-place 알고리즘을 사용해 공간 복잡도를 O(1)로 최적화
• 배열의 인덱스-값 매핑을 이해하는 것이 핵심
• nums[i]가 1 ≤ x ≤ n 범위에 있을 때만 조작 (0, 음수, n+1 이상은 무시)