(Python3) - LeetCode (Medium) : 3310. Remove Methods From Project

https://leetcode.com/problems/remove-methods-from-project

Remove Methods From Project - LeetCode

stack dfs로 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

📑 인접그래프를 저장할 2차원 배열 graph를 선언합니다. n행은 method n이 호출하는 caller이고 저장될 원소는 callee가 되므로 invocations의 원소를 순회하며 graph를 갱신합니다.

📑 의심되는 노드를 저장할 suspicious를 선언합니다.

📑 그래프를 순회할 노드를 저장할 stack을 선언합니다. 순회할 첫 노드인 k를 stack에 저장합니다.

📔 풀이과정

📑 k가 직접 또는 간접적으로 호출하는 모든 메서드를 탐색하여 suspicious에 저장합니다.

1. stack에서 탐색할 노드 node를 꺼냅니다.
2. 0 → 1 → 0과 같은 순환 호출에서 무한 탐색하는 것을 막기 위해, 이미 suspicious에 포함된 노드라면 건너뜁니다.
3. 현재 node는 k에서 도달 가능한 메서드이므로 suspicious에 추가합니다.
4. node가 호출하는 모든 인접 메서드를 다음 탐색 대상으로 stack에 추가합니다.

이 과정을 통해 k가 직접 또는 간접적으로 호출하는 모든 메서드를 찾습니다.

📑 이후 invocations를 다시 순회하며 의심스러운 메서드들을 제거할 수 있는지 검사합니다.

caller not in suspicious and callee in suspicious

위 조건은 정상 메서드가 의심스러운 메서드를 호출하는 경우를 의미합니다.

문제에서는 의심스러운 메서드를 모두 제거할 수 없는 경우 아무것도 제거하지 않아야 하므로, 이 조건을 하나라도 발견하면 모든 메서드를 반환합니다.

return list(range(n))

외부에서 의심스러운 메서드를 호출하는 경우가 없다면 suspicious에 포함되지 않은 메서드만 반환합니다.

📑 시간 복잡도

메서드의 개수를 n, 호출 관계의 개수를 m이라고 하겠습니다.

• 인접 리스트 생성: O(m)
• DFS 탐색: O(n + m)
• 외부에서 의심스러운 메서드를 호출하는지 검사: O(m)
• 남은 메서드 생성: O(n)

따라서 전체 시간 복잡도는:

O(n + m)

---

📑 공간 복잡도

• 인접 리스트 graph: O(n + m)
• 의심스러운 메서드 집합 suspicious: O(n)
• DFS 탐색용 stack: O(n)

따라서 전체 공간 복잡도는:

O(n + m)

📔 정답 출력 | 반환

정상 메서드가 의심스러운 메서드를 호출한다면 모든 메서드를 반환합니다.

그렇지 않다면 의심스러운 메서드를 제외한 나머지 메서드 목록을 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(n)]
        for caller, callee in invocations:
            graph[caller].append(callee)
        suspicious = set()
        stack = [k]
        while stack:
            node = stack.pop()
            if node in suspicious:
                continue
            
            suspicious.add(node)
            for next_node in graph[node]:
                stack.append(next_node)

        for caller, callee in invocations:
            if caller not in suspicious and callee in suspicious:
                return list(range(n))

        return [method for method in range(n) if method not in suspicious]

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.