LeetCode [1791]: Find Center of Star Graph

📌 LeetCode [1791]: Find Center of Star Graph

🔗 문제 링크

---

문제 설명 📄

Star Graph에서 중심 노드를 찾는 문제입니다.
Star Graph는 하나의 중심 노드가 모든 다른 노드와 직접 연결된 형태의 그래프입니다.

edges가 주어질 때, Star Graph의 중심 노드를 반환하세요.

---

Solution 💻

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        pattern = {}

        for one, two in edges:
            if one in pattern:
                return one
            if two in pattern:
                return two
            pattern[one] = 1
            pattern[two] = 1

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • edges 리스트를 순회하며 각 노드를 pattern 딕셔너리에 추가하거나 확인.
• 공간 복잡도: O(n)
  • 최대 n개의 노드를 저장하는 딕셔너리 사용.

---

리팩토링 🛠️

개선된 코드

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        # 중심 노드는 항상 첫 두 간선의 공통 노드
        return edges[0][0] if edges[0][0] in edges[1] else edges[0][1]

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도: O(1)
  • 첫 두 간선만 확인하므로 상수 시간.
• 공간 복잡도: O(1)
  • 추가 메모리 사용 없음.

---