티스토리 뷰

반응형

프로그래머스의 도넛과 막대 그래프 문제를 풀면서 시간초과가 발생했다.

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

from collections import defaultdict


def solution(edges):
    answer = [0, 0, 0, 0]
    graph = defaultdict(list)
    out_ = defaultdict(int)
    in_ = defaultdict(int)
    for e in edges:
        graph[e[0]].append(e[1])
        out_[e[0]] += 1
        in_[e[1]] += 1

    centor_node = [g for g in graph.keys() if out_[g] >=2 and in_[g] == 0][0]
    answer[0] = centor_node

    doughnut = 0
    bar = 0
    eight = 0
    visited = set() # 시간 초과 발생을 일으킨 부분
    for start_node in graph[centor_node]:
        visited.add(start_node)
        curr = start_node
        while curr:
            if out_[curr] == 0:
                bar += 1
                break
            elif out_[curr] == 2:
                eight+=1
                break
            curr = graph[curr][0]
            if curr in visited and out_[curr] == 1:
                doughnut+=1
                break
            visited.add(curr)

    answer[1] = doughnut
    answer[2] = bar
    answer[3] = eight
    return answer

위의 코드를 보면 visited 변수 부분에 원래는 리스트 자료구조를 사용했다. 리스트 자료구조를 사용하니 시간초과가 발생해서 set 자료구조로 변경 했더니 시간초과가 해결이 되었다. set은 중복된 값을 허용하지 않는 자료구조로 알고 있는데 두가지 자료구조의 속도 차이가 있는 것 같아 알아보았다.

 

 

ChatGPT 답변

  1. 리스트(List):
    • 탐색(Search): 리스트는 순차적으로 요소를 찾아야 하기 때문에 시간 복잡도가 O(n)입니다. 즉, 리스트의 길이에 비례하여 시간이 증가합니다.
    • 삽입/삭제(Insertion/Deletion): 리스트의 끝에 추가하는 작업은 평균적으로 O(1)이지만, 중간에 삽입하거나 삭제하는 경우 O(n) 시간이 소요됩니다.
  2. 집합(Set):
    • 탐색(Search): 집합은 해시 테이블을 사용하기 때문에, 요소를 찾는 작업이 평균적으로 O(1) 시간 복잡도를 가집니다. 따라서 대량의 데이터가 있을 때 매우 빠릅니다.
    • 삽입/삭제(Insertion/Deletion): 집합에 요소를 추가하거나 제거하는 작업도 평균적으로 O(1)이므로 리스트보다 훨씬 빠릅니다.

 

결과적으로 정리해보면 아래와 같이 차이점이 있다는 것을 알 수 있다. 순서가 중요하지 않는 경우 set을 사용하면 탐색 속도면에서 더욱 빠르다!

 

Aspect 리스트 (List) 집합 (Set)
시간 복잡도 (탐색) O(n) - 순차 탐색 O(1) - 해시 기반 탐색
시간 복잡도 (삽입/삭제) O(n) (중간 삽입/삭제), O(1) (끝 삽입/삭제) O(1) - 평균
순서 보장 보장됨 보장되지 않음
인덱싱 가능 여부 가능 불가능
중복 허용 여부 허용 허용하지 않음
메모리 사용량 효율적 (해시 테이블 없음) 비효율적 (해시 테이블로 인한 메모리 사용 증가)
반응형
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함