[프로그래머스] 도넛과 막대 그래프 (python)

 

1️⃣ 문제

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

2️⃣ 필요한 개념

차수 기반 문제 판별하기

1. 입력 크기 크다 → 탐색 괜찮나?
2. 문제 설명이 구조적 정의(사이클, 끝점, 교차점) → 차수로 풀 수 있나?
3. 출력이 개수만 요구됨 → 구체 탐색 필요 없네?

3️⃣ 풀이

def solution(edges):
    answer = []
    in_out_list = [[0,0] for _ in range(1000000+1)]
    if (len(edges) == 1):
        return 1, 1, 0, 0
    for edge in edges:
        a,b = edge 
        in_out_list[a][1] += 1
        in_out_list[b][0] += 1
    bar_count   = sum(1 for i,o in in_out_list if i==1 and o==0)
    if (bar_count == 0):
        bar_count   = sum(1 for i,o in in_out_list if i==0 and o==1)
    eight_count = sum(1 for i,o in in_out_list if i>=2 and o>=2)
    print(in_out_list[:10])
    
    max_o = -1
    max_k = -1
    for k in range(len(in_out_list)):
        i_o = in_out_list[k]
        i, o = i_o
        if (i == 0 ):
            if (max_o < o):
                max_o = o
                max_k = k
    start_node = max_k
    print(start_node)
    max_out = in_out_list[max_k][1]
    donut_count = max_out - bar_count - eight_count
    return start_node, donut_count, bar_count, eight_count