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

문제

프로그래머스

 

풀이 아이디어 

각 도형의 특징을 고려하면 쉽게 풀 수 있다. 

• 임의로 생성된 정점: 임의로 생성된 정점은 들어오는 간선은 없으며 나가는 간선만 존재한다. 또한 도형은 최소 2개 이상 존재하니 나가는 간선은 2개 이상이다. (in_line=0, out_line>=2) 추가적으로 임의의 정점은 모든 도형과 1개의 간선으로 연결되어 있으니 나가는 간선(out_line)의 개수가 전체 도형의 개수와 같다. 
• 막대그래프: 막대그래프는 들어오는 간선이 0개인 정점과 나가는 간선이 0개인 정점이 하나 존재한다. 그러나 임의의 정점으로 인해 들어오는 간선이 0개인 경우를 고려할 경우 예외 케이스가 다수 발생한다. 그러므로 나가는 간선이 0개인 정점의 개수를 구하면 막대 그래프의 개수를 구할 수 있다. (out_line = 0)
• 도넛 모양 그래프: 전체 도형의 개수 - 막대그래프 수 - 도넛 그래프 수
• 8자 모양 그래프: 8자 모양은 필연적으로 가운데에 들어오고 나가는 간선이 2개인 정점이 하나씩 존재한다. 그러므로 in_line>=2, out_line=2인 정점의 개수를 구하면 8자 모양 그래프의 개수를 구할 수 있다. in_line>=2로 설정하는 이유는 임의의 정점으로 인해 들어오는 간선이 하나 더 생길 수 있기 때문이다. 

시간 복잡도: O(n), 반복문 1개 중첩 

풀이하면서 생겼던 문제점

테스트 케이스 35번에서 문제가 계속해서 틀리는 경우 발생. 원인을 분석해본 결과 35번에서 들어오고 나가는 간선의 개수가 0개인 정점이 존재한다. 형태는 막대 그래프가 n=1일때와 같지만 도형으로 취급되지 않아서 임의로 생성된 정점과 연결되지 않았다. 약간 억지처럼 느껴지는 테스트 케이스. 만일 이 문제를 풀 경우 들어오고 나가는 간선의 개수가 0개인 경우를 추가해주면 해결할 수 있다.  (in_line=0, out_line=0을 예외처리)

 

 

코드 

def solution(edges):
    total = 0 
    max_id = 0
    answer = [0]*4
    for edge in edges:
        if max_id < max(edge):
            max_id = max(edge)
    
    in_list = [0]*(max_id)
    out_list = [0]*(max_id)
    
    for edge in edges:
        out_list[edge[0]-1] += 1
        in_list[edge[1]-1] += 1
    
    for i in range(len(in_list)):
        if out_list[i] == 0 and in_list[i]>=1:
            answer[2]+=1
        elif (in_list[i]>=2 and out_list[i]>=2):
            answer[3]+=1
        elif (in_list[i]==0 and out_list[i]>1):
            answer[0] = i+1
            total = out_list[i]
    
    answer[1] = total-answer[2]-answer[3]
    
    return answer