144일 (817. Linked List Components) Set, LinkedList

You are given the head of a linked list containing unique integer values and an integer array nums that is a subset of the linked list values.

Return the number of connected components in nums where two values are connected if they appear consecutively in the linked list.

 

Example 1:

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.

Example 2:

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

 

Constraints:

• The number of nodes in the linked list is n.
• 1 <= n <= 10^4
• 0 <= Node.val < n
• All the values Node.val are unique.
• 1 <= nums.length <= n
• 0 <= nums[i] < n
• All the values of nums are unique.

 

- 접근방법

head는 오름차순으로만 나오지 않고 nums는 정렬이 의미가 없다.

nums[0] ~ nums[n]과 각각의  head.val를 비교하여 같을때, 연결된 구성요소의 개수를 세서 리턴하는 문제이다.

(연결된 구성요소의 길이가 1이어도 1개, 길이가 셀 수없이 길어도 1개로 센다.)

 

head = [1,5,2,4,3]  nums = [3,1,2]일때 head의 1과 2와 3이 nums와 같으므로 3을 리턴하면 된다.

→ head = [1,5,2,4,3]은 각각 3개이므로 3을 리턴한다.)

head = [1,5,2,4,3]  nums = [5,2,1]일때 head의 1과 5와 2가 nums와 같으므로 1를 리턴하면 된다.

→ head = [1,5,2,4,3] 의 152는 연속적으로 이루어졌으므로 1개가 되며 1을 리턴한다.)

 

1. node들과 nums의 모든 값은 고유한 값이므로 nums를 자료구조 set에 저장한다.

→ 자료구조 set의 set.contains()는 해시함수가 충돌이 일어나지 않는 한 O(1)의 시간복잡도이다.

따라서 nums를 set에 저장하면 head의 각각의 값들이 nums에 속하는지 O(1)의 시간복잡도로 모두 확인가능하다.

 

2. 현재 head값이 set에 포함되어있는지 확인하며 연결된 구성요소의 개수를 세야한다.

구성요소가 모두 연결되어있어도 개수는 1개로 세어야하고, 구성요소가 1개인 경우에도 개수는 1개로 센다.

따라서 구성요소가 연속적으로 연결되어있는경우 boolean flag 구분하여 연속적으로 노드가 이어지는 경우라도 최초의 1번만 개수로 센다.

 

 

- 코드

 /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> set = new HashSet<>();
        boolean flag = false;
        int answer = 0;

        for(int num : nums) { // 1
            set.add(num);
        }

        while(head != null) { // 2
            if(set.contains(head.val)) {
                if(!flag) {
                    answer++;
                    flag = true;
                }
            } else flag = false;
            head = head.next;
        }

        return answer;
    }
}

 

문제의 난이도 자체는 쉬운편이라고 생각하지만 이 문제는 설명이 생략되어있기 때문에 동작조건을 오해하기가 쉽다..

따라서 직접 테스트케이스를 입력하여 값들을 찍어봐야만 정확히 동작조건을 알 수있다.

 

설명이 생략되어 헛걸음을 하였어도, 모든 값들은 고유한 값이므로 set을 사용할 생각을 떠올리는건 어렵지않다.

 

 

 

 

https://leetcode.com/problems/linked-list-components/

LeetCode - The World's Leading Online Programming Learning Platform