[programmers/py] 도넛과 막대 그래프

도넛과 막대 그래프

https://school.programmers.co.kr/learn/courses/30/lessons/258711

문제 설명

• 막대, 8자, 도넛 그래프가 있음
• 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 순서대로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

문제 풀이

각 그래프를 보면 규칙을 찾을 수 있는 그래프가 있다.
막대 그래프는 하나의 노드가 나가는(output)이 없고 들어오는 간선(input)만 존재
8자 그래프는 중앙 노드의 나가는 간선이 2개로 고정
위 두 가지 규칙을 활용해 그래프 수를 구하고 생성한 정점의 나가는 간선 - 막대 - 8자를 통해 도넛 그래프를 구해준다.

def solution(edges):    
    answer = [] # 정점, 도넛, 막대, 8자
    input_count = [0 for _ in range(1000001)]
    output_count = [0 for _ in range(1000001)]
    created_node = -1
    doughnut_count = 0
    stick_count = 0
    eight_count = 0
    max_value = -1
    
    for a, b in edges:
        max_value = max(max_value,a,b) #가장 큰 노드, 반복문을 위해
        output_count[a] += 1
        input_count[b] += 1
        
    for i in range(1, max_value + 1):
        if input_count[i] == 0 and output_count[i] >= 2:
            created_node = i
        elif input_count[i] >= 1 and output_count[i] == 0: # 상위? 노드의 ouput은 0으로 고정
            stick_count += 1
        elif input_count[i] >= 2 and output_count[i] == 2: # 중앙 노드의 ouput은 2로 고정
            eight_count += 1
    doughnut_count = output_count[created_node] - stick_count - eight_count
    
    return [created_node, doughnut_count, stick_count, eight_count]