3/24 풀이

https://leetcode.com/problems/count-the-number-of-complete-components/description/?envType=daily-question&envId=2025-03-22

 

2685. Count the Number of Complete Components

모두 연결된 그래프

 

3-4-5는 연결되지 않음

 

 

그래프를 순회하면서, 연결된 그래프인 경우에만 결과값을 더해주는 문제였다.

나름 쉽다고 생각해서 접근했지만, 생각보다 벽에 막혔다. 처음에 사이클을 판별하는 DFS를 통해서 문제 접근을 했지만, 3-4나 5와 같은 그래프 형태도 연결된 그래프로 가정했기 때문에 틀렸다.

 

다른 사람의 풀이를 참고해서야 힌트를 얻을 수 있었는데, 매번 DFS를 순회할 때 마다 각 노드 번호를 리스트에 삽입해준다.

예를 들어서 0에서 출발해서 DFS가 끝날 시점에는 리스트에는 [0,1,2]가 담겨있을 것이다.

 

이 때, 해당 리스트를 다시 순회하면서 현재 노드의 길이와 리스트의 길이를 비교한다.

현재 노드가 0 이라면, 연결된 노드는 [1,2]이기 때문에 2고, 전체 리스트는 3이다. 이 때, 연결된 노드의 길이가 `전체 -1`이라면 연결된 그래프로 간주한다.

왜? 자기 자신을 제외한 노드의 갯수가 전체 - 1이기 때문에 연결된 그래프로 판단하는 것이다.

 

밑의 예제인 `5 - 3 - 4`를 보자.

3과 연결된 노드는 [4,5] 이므로 전체 리스트 [3,4,5]일 때 성립한다.

하지만, 4나 5일때는 연결되어 있는 노드가 3밖에 없다. 연결되지 않았다는 의미기 때문에 건너뛰어야 한다.

이 때, break문을 통해 전체 그래프 탐색을 종료해야 중복 탐색을 하지 않는다.

 

정답

class Solution {
    List<List<Integer>> graph = new ArrayList<>();
    int cnt = 0;
    int [] deg;
    public int countCompleteComponents(int n, int[][] edges) {
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        deg = new int[n];
        for(int [] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        boolean [] visited = new boolean[n];
        for(int i = 0; i < n; i++) {
            if (!visited[i]) {
                List<Integer> list = new ArrayList<>();
                dfs(i, visited, list);
                boolean flag = true;
                for(int next : list) {
                    if (graph.get(next).size() != list.size() - 1) {
                        flag = false;
                        break;
                    }
                }
                if (flag) cnt++;
            }
        }
        return cnt;
    }

    public void dfs(int start, boolean[] visited, List<Integer> list ) {
        list.add(start);
        visited[start] = true;
        for(int next : graph.get(start)) {
            if (!visited[next]) {
                dfs(next, visited, list);
            }
        }
    }
}

 

 

https://leetcode.com/problems/count-days-without-meetings/?envType=daily-question&envId=2025-03-24

 

3169. Count Days Without Meetings

Example 1:
Input: days = 10, meetings = [[5,7],[1,3],[9,10]]
Output: 2
Explanation:There is no meeting scheduled on the 4th and 8th days.

Example 2:
Input: days = 5, meetings = [[2,4],[1,3]]
Output: 1
Explanation:There is no meeting scheduled on the 5th day.

Example 3:
Input: days = 6, meetings = [[1,6]]
Output: 0
Explanation:Meetings are scheduled for all working days.

 

방문하지 않은 날짜를 구하는 문제였다. 단순 구현(그리디) 방식으로 문제를 접근했다.

일단, 시작 날짜를 오름차순으로 정렬하는 것이 필요해보였기 때문에 정렬해주었다. (meetings 길이 = 10만)

 

output에 값을 더해주는건 3가지 케이스가 존재한다.

1. start가 1보다 클 때: meetings의 시작 날짜에서 1을 빼준 값을 더해줘야 한다.
2. end가 days보다 작을 때: 마찬가지로 days에서 end를 빼줘야 한다.
3. 이전의 end값이 현재 start보다 작을 때
   
   1. 예제 1번의 [1,3] [5,7]일 때 방문하지 않은 날짜 4가 추가되어야 하는 경우다.

 

정답

class Solution {
    // days 10억 meetings 10만
    public int countDays(int days, int[][] meetings) {
        int res = 0;
        Arrays.sort(meetings, (a,b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return Integer.compare(a[0], b[0]);
        });
        int st = meetings[0][0];

        int before = 0;
        for(int [] meeting : meetings) {
            int start = meeting[0];
            int end = meeting[1];
            if (before != 0 && before + 1 < start) {    
                res += (start - before - 1);
            }

            if (before < end)
                before = end;
        }

        res += (days - before);
        
        if (st > 1) { // 첫 시작이 1일 이상이라면
            res += (st - 1);
        }
        return res;
    }
}