[프로그래머스] [2024 카카오 기출] 도넛과 막대 그래프

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

프로그래머스

문제 풀이

이 문제는 각 노드와 각 그래프의 특징을 빠르게 파악해서 그래프를 찾는 것이 중요하다.

• '생성된 정점'은 나가는 간선의 수가 2 이상이고, 들어오는 간선의 수가 0이다.
• '막대 모양 그래프'의 수는 나가는 간선의 수가 0, 들어오는 간선의 수가 1인 노드의 개수와 같다.
• '8자 모양 그래프'의 수는 나가는 간선의 수가 2, 들어오는 간선의 수도 2인 노드의 개수와 같다.
• '도넛 모양 그래프'는 '생성된 정점'의 나가는 간선의 수에서 막대 모양 그래프와 8자 모양 그래프의 개수를 빼서 구한다.
• 이때, 막대 모양 그래프와 8자 모양 그래프의 경우 '생성된 정점'에서 들어오는 간선이 존재하므로 각각 1 이상, 2 이상으로 조건을 설정한다.

이러한 규칙을 찾은 후, 주어진 간선 리스트를 통해 

1. 노드마다 들어오는 간선 수, 나가는 간선 수 계산하기

2. 위에서 구해진 간선 수 리스트를 통해 생성한 정점, 막대 그래프, 8자 모양 그래프, 도넛 모양 그래프 를 찾아야 한다.

코드 구현

def solution(edges):
    def count_edges(edges):
        # 각 노드별로 간선의 수를 추가할 딕셔너리
        # 딕셔너리 value = 나가는 간선 수, 들어오는 간선 수
        edge_counts = {}
        # a에서 b로 향하는 간선
        for a,b in edges:
            # 간선들 순회하면서 딕셔너리에 없으면 value 추가해주기
            if not edge_counts.get(a):
                edge_counts[a] = [0,0]
            if not edge_counts.get(b):
                edge_counts[b] = [0,0]
            
            edge_counts[a][0] += 1
            edge_counts[b][1] += 1
        return edge_counts
    
    def check_answer(edge_counts):
        answer = [0,0,0,0]
        for key, counts in edge_counts.items():
            # 생성된 정점
            if counts[0] >= 2 and counts[1] == 0:
                answer[0] = key
            # 막대 모양 그래프
            elif counts[0] == 0 and counts[1] >= 1:
                answer[2] += 1
            # 8자 모양 그래프
            elif counts[0] == 2 and counts[1] >= 2:
                answer[3] += 1
            # 도넛 모양 그래프
            answer[1] = edge_counts[answer[0]][0] - answer[2] - answer[3]
        return answer
    
    edge_counts = count_edges(edges)
    answer = check_answer(edge_counts)
    return answer

이렇게 풀었더니 런타임 에러가 많이 떠서 추후에 고쳐보려고 한다.

런타임 에러를 해결하신 분의 글도 참고에 올려놓겠다.

참고

이 글은 카카오 인턴십 코딩테스트를 2일 앞두고 빠르게 기출을 풀기 위해 연습해본 글이다.

구현 방법을 바로 생각하는게 어려워서 다른 글을 참고하며 직접 구현해 보았다.

https://velog.io/@mino0121/ProgrammersPython-%EB%8F%84%EB%84%9B%EA%B3%BC-%EB%A7%89%EB%8C%80%EA%B7%B8%EB%9E%98%ED%94%84

[Programmers/Python] 도넛과 막대그래프

https://s5unnyjjj.tistory.com/81

[홀로 하는 코딩 공부] 도넛과 막대 그래프(Python)