[카카오 기출 - Python] 도넛과 막대 그래프

작년에 코테 응시하면서 풀어 봤던 문제

잘 기억은 안나는데, 어찌 저찌 풀이를 해서 테스트 케이스 몇 개는 통과했던 기억...

근데 전체 통과는 못했던 걸로 기억한다

 

https://tech.kakao.com/posts/610

2024 카카오 겨울 인턴십 코딩테스트 문제해설 - tech.kakao.com

 

공식 문제 해설을 보면, 생성된 노드와 각 그래프가 갖는 특성을 기반으로

생성된 노드 번호와 각 그래프의 개수를 구한다

 

이러한 특성을 활용하기 위해서는 입력으로 주어지는 간선 정보를 정점별로 저장해야 한다.

정점이 몇 개 인지 모르기 때문에 딕셔너리 자료 구조를 사용한다.

 

def solution(edges):
    # {노드 번호 : [나가는 간선, 들어오는 간선]}
    edge_counts = {}
    for a, b in edges:
        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
    
    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] > 0:
            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

 

간선 정보를 바탕으로 정보를 잘 저장하고, 특성 파악만 한다면

특별한 알고리즘 없이 쉽게 풀 수 있는 문제였다.

 

딕셔너리 자료형을 사용하는 풀이가 별로 없어서 딕셔너리 자료형 연습하기 좋은 문제였던 것 같다!

 

 

참고 자료

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