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

프로그래머스

사용 언어: Python

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 처음에는 아래와 같이 작성해보았다. 

def solution(edges):
    answers = [0, 0, 0, 0]
    n = max(max(edges))+1

    edges_in, edges_out = [0]*n, [0]*n
    for i, j in edges:
        edges_in[i] += 1
        edges_out[j] += 1

    for i in range(1, n):
        if edges_in[i] >= 2 and edges_out[i] >= 2:
            answers[3] += 1
        if edges_out[i] == 0 and edges_in[i] == 1:
            answers[1] += 1
        if edges_out[i] == 0 and edges_in[i] >= 2:
            answers[0] = i

    answers[2] = edges_in[answers[0]] - (answers[1] + answers[3])
    
    return answers

 

▶ 고민을 해보다 뭐가 문제인지 모르겠어서 다른 블로그를 참조했다.

Reference: 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] 도넛과 막대그래프

 

▶ 비교 결과 for문 안에서 도넛 모양 그래프 수를 구하는 것이 아니라, 막대 모양 그래프 수를 구한다.

  - 도넛 모양 그래프의 경우, 계산법이 틀렸다.

  - 막대 모양이나 8자 모양 그래프는 나가는 간선과 들어오는 간선으로 판단한다.

  - 재방문되는 엣지가 발견된다면 해당 엣지에서 나가는 간선이 1개인 경우가 도넛 모양 그래프이다.

  - 결론, 도넛 모양 그래프는 막대 모양이나 8자 모양에 비해 계산이 복잡하니 위의 블로그처럼 도넛 모양 구하고 막대 모양 구하고 총합에서 빼는 걸로 한다.

▶  위의 블로그처럼 해당 부분을 수정해본다. 

def solution(edges):
    answers = [0, 0, 0, 0]
    n = max(max(edges))+1

    edges_in, edges_out = [0]*n, [0]*n
    for i, j in edges:
        edges_in[i] += 1
        edges_out[j] += 1

    for i in range(1, n):
        if edges_in[i] >= 2 and edges_out[i] >= 2:
            answers[3] += 1
        if edges_out[i] > 0 and edges_in[i] == 0:
            answers[2] += 1
        if edges_out[i] == 0 and edges_in[i] >= 2:
            answers[0] = i

    answers[1] = edges_in[answers[0]] - (answers[2] + answers[3])
    
    return answers

 

▶ 막대 모양과 도넛 모양의 수 계산 오류가 맞았다. 거의 다 통과다. 이제 나머지 에러를 살펴본다. 

▶ 런타임에러가 발생하였다. 런타임에러는 대게 배열의 크기가 안맞는경우 대부분이다.

  - 문제를 다시 읽어보니 edges의 최대 길이 1,000,000이다.

  - edges의 최대 값 만큼 edges_in, edges_out 배열을 만들지 않았다.

  - 그래서 최대 길이 만큼 두 배열을 만들어주어 다시 실행해본다.

def solution(edges):
    answers = [0, 0, 0, 0]
    n = 1000000
    edges_in, edges_out = [0]*n, [0]*n
    for i, j in edges:
        edges_in[i] += 1
        edges_out[j] += 1

    for i in range(1, n):
        if edges_in[i] >= 2 and edges_out[i] >= 2:
            answers[3] += 1
        if edges_out[i] > 0 and edges_in[i] == 0:
            answers[2] += 1
        if edges_out[i] == 0 and edges_in[i] >= 2:
            answers[0] = i

    answers[1] = edges_in[answers[0]] - (answers[2] + answers[3])
    
    return answers

 

▶ 통과하였다. 하지만 효율성 측면에서 보면 각각의 테스트 시, 소요 되는 시간이 길다. 해당 시간을 줄여보기 위해 코드를 수정해본다. 

  - answers 값을 구해주는 for문을 1,000,000만큼이 아닌 edges내의 최대 값만큼만 진행해준다.(edges 내에 최대 값은 edge의 개수 이다.)

  - edges 내에 1,000,000 값이 없는데 그 만큼 반복해주면 시간이 더 소요될 것이기 때문이다.

def solution(edges):
    answers = [0, 0, 0, 0]
    n = 1000000
    maxV = 0
    edges_in, edges_out = [0]*n, [0]*n
    for i, j in edges:
        edges_in[i] += 1
        edges_out[j] += 1
        maxV = max(i, j, maxV)

    for i in range(1, maxV+1):
        if edges_in[i] >= 2 and edges_out[i] >= 2:
            answers[3] += 1
        if edges_out[i] > 0 and edges_in[i] == 0:
            answers[2] += 1
        if edges_out[i] == 0 and edges_in[i] >= 2:
            answers[0] = i

    answers[1] = edges_in[answers[0]] - (answers[2] + answers[3])
    
    return answers

 

 

▶ 이전에 비해서 확연하게 시간이 단축 되었다.

  - 특히 테스트1~7까지는 이전에는 걸리는 소요 시간이 세자리 수였는데 두자리로 단축되었다.

  - 하지만 테스트 21 경우 시간이 조금 더 소요 된다.

▶ 단축시킬만한 다른방안을 고민해보다 아래와 같은 시도를 해본다.

 - 배열을 edges의 최대 길이인 1,000,000만큼 다 만드는 것이 아니라 defaultdict를 사용하여 유동적으로 사용하게 끔 해보려한다. 

from collections import defaultdict

def solution(edges):
    answers = [0, 0, 0, 0]
    maxV = 0
    edges_in, edges_out = defaultdict(int), defaultdict(int)
    for i, j in edges:
        edges_in[i] += 1
        edges_out[j] += 1
        maxV = max(i, j, maxV)

    for i in range(1, maxV+1):
        if edges_in[i] >= 2 and edges_out[i] >= 2:
            answers[3] += 1
        if edges_out[i] > 0 and edges_in[i] == 0:
            answers[2] += 1
        if edges_out[i] == 0 and edges_in[i] >= 2:
            answers[0] = i

    answers[1] = edges_in[answers[0]] - (answers[2] + answers[3])
    
    return answers

 

▶ 테스트1~7은 1ms도 안 걸릴 정도로 소요되어 확연하게 시간이 줄어들었다. 효과는 있었나보다. 하지만 테스트 21은 거의 2배가 증가하였다.

▶ 전반적으로 시간이 다 줄어든 것은 아니지만 일부 테스트 케이스에 대해 확연하게 줄어드는 것을 보니 좋은 시도 였다고 생각한다. 

 

Reference: 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

velog

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.