[LeetCode] 817. Linked List Components

문제

연결 리스트 head와, 리스트 값의 부분집합인 배열 nums가 주어진다.
리스트에서 연속으로 이어진 nums 값들의 묶음(컴포넌트)이 몇 개인지 구한다.

head = 0 -> 1 -> 2 -> 3,  nums = [0, 1, 3]
답: 2  ({0, 1}, {3})

접근

처음 시도: nums를 기준으로 순회 ❌

nums를 앞에서부터 읽으면서 "직전 값의 next가 지금 값인가"로 연결 여부를 판단했다.

하지만 nums의 순서는 리스트 순서와 상관없다.

head = 0 -> 1 -> 2,  nums = [1, 0]
정답 1, 출력 2

기준 바꾸기: 리스트를 순회 ✅

• nums는 Set으로 바꿔서 포함 여부 확인에만 쓴다.
• 리스트를 순회하다가 컴포넌트의 끝을 만나면 하나씩 센다.

컴포넌트의 끝이 되는 조건:

1. 현재 노드가 Set에 있고
2. 다음 노드가 없거나 Set에 없다

주의할 점

다음 조건은 틀린 조건이다.

if (node.next && !numSet.has(node.next.val)) components++;

node.next가 null이면 조건 전체가 false가 되므로, 리스트 끝까지 이어진 컴포넌트를 세지 못한다.

head = 0 -> 1 -> 2,  nums = [1, 2]
정답 1, 출력 0

!node.next ||로 고쳐서 "다음 노드가 없음"도 끝으로 처리해야 한다.

코드

function numComponents(head: ListNode | null, nums: number[]): number {
  const numSet = new Set<number>(nums);
  let components = 0;

  for (let node = head; node; node = node.next) {
    if (!numSet.has(node.val)) continue;
    if (!node.next || !numSet.has(node.next.val)) components++;
  }

  return components;
}

복잡도

• 시간: O(n)
• 공간: O(m) (m = nums 길이)