프로그래머스 도넛과 막대 그래프 | Python

🔎 문제 설명

💚 Level 2

- 난이도 ★★★☆
- 그리디
- [2024 KAKAO WINTER INTERNSHIP]

프로그래머스 Level 2 치고 풀기 쉽지 않았던 문제다. 처음엔 당연히 그래프가 나와서 그래프탐색으로 도넛 모양, 막대 모양, 8자 모양 그래프를 각각 구하려고 했는데 edge 개수가 1M 개라는 점에서 시간초과가 날 것이라고 예상했다. 또한, 도넛과 8자 모양을 세는 걸 고민하는 데 시간을 많이 썼다.

✅ input 간선과 output 간선으로 푸는 문제

• 📍 생성한 정점의 번호
  • 이해하기 어려웠음
  • 이 정점을 기준으로 도넛, 막대, 8자 모양 그래프가 생김
  • output 만 존재하는 정점
• 🍩 도넛 모양 그래프
  • 루트에서 시작해서 루트로 돌아올 수 있는 그래프
  • 8자 모양 그래프와 어떻게 구분할지 생각해야 함
    • 생성한 정점 output 개수 중 다른 모양 그래프 개수 빼면 될 듯

      
      

• 🥖 막대 모양 그래프
  • 마지막 노드 기준으로 input 1개 이상, output 0개
    
• 🥨 8자 모양 그래프
  • 루트 1개를 기준으로 도넛 모양 그래프가 2개 존재
  • input 2개 이상, output 2개

💻 내 코드

def solution(edges):
    N = 0 # 마지막 정점 번호

    index, doughnut, bar, eight = 0, 0, 0, 0
    input_edge = [0 for _ in range(1000001)]
    output_edge = [0 for _ in range(1000001)]
    
    for a, b in edges:
        N = max(N, a, b)
        output_edge[a] += 1
        input_edge[b] += 1
        
    for node in range(1,N+1):
        if input_edge[node] == 0 and output_edge[node] >= 2:
            index = node
        if input_edge[node] >= 2 and output_edge[node] == 2:
            eight += 1
        if input_edge[node] >= 1 and output_edge[node] == 0:
            bar += 1

    doughnut = output_edge[index] - eight - bar
    return [index, doughnut, bar, eight]

개인적으로 문제 이해에 도움되었던 페이지를 남긴다.
✔️ [해설] 초보자를 위한 상세한 해설