[Java]LeetCode 817. Linked List Components

LeetCode 817. Linked List Components  -  Java

 

문제 :

Linked List를 주고 그 Linked List의 subset을 준다.

주어진 Linked List를 기준으로 subset List가 순서대로 이어진 그룹이 몇 개인지 센다.

Input: head = [0,1,2,3], nums = [0,1,3]
Output: 2
Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components.
[0, 1] , [3] -> 2

 

 

HashSet 생성

HashSet의 특징 : 중복을 허용하지 않는다.

Set<Integer> set = new HashSet<>();

---

 

nums를 HashSet에 추가한다.

for(int i: nums){
    set.add(i);
}

---

 

Component의 연결이 마지막이라는 것을 알 수 있는 조건
1 .head 노드의 마지막인 경우
2. 현재 노드 기준 다음 노드의 값이 nums에 포함되지 않았을 경우

Component의 연결이 유지될 수 있는 조건
1. 현재 노드의 값이 HashSet에 포함되어 있는 경우

 

 

---

head를 처음부터 검사하면서 위 두 조건을 적용해 노드들을 그룹핑해주며 result 값을 더해준다.

 

while(head != null){
    if(set.contains(head.val) && (head.next == null || !(set.contains(head.next.val)) ) ){
        result++;
    }
    head = head.next;
}

---

 

결  과

class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> set = new HashSet<>();
        int result =0; 

        for(int i: nums){
            set.add(i);
        }

        while(head != null){
            if(set.contains(head.val) && (head.next == null || !(set.contains(head.next.val)) ) ){
                result++;
            }
            head = head.next;
        }

        return result;
    }
}