[프로그래머스] > LV.2 > 타겟넘버

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

프로그래머스

 

처음 코드는 다음과 같다.

개인적은 dfs(깊이 우선 탐색) 보다 bfs(너비 우선 탐색)의 방식이 나한테 잘 맞는다고 생각했다.

그러나 이 코드에서는 시간 초과가 떴는데, 문제점을 살펴본 결과 pop(0)의 과정에서 n개의 모든 원소를 확인하여 빼기때문에 시간 복잡도는 O(n)이라고 한다.

만약 depue의 자료형이라면 popleft()을 활용해 O(1)의 시간복잡도로 문제를 풀이할 수 있다.

def solution(numbers, target):
    answer = 0
    q = []
    n = len(numbers)
    q.append([numbers[0],0])
    q.append([-(numbers[0]), 0])
    while q:
        num, index = q.pop(0)
        index += 1
        if index != n:
            q.append([num + numbers[index], index])
            q.append([num - numbers[index], index])
        else:
            if num == target:
                answer += 1
    return answer

 

from collections import deque를 선언하고

popleft() 함수를 활용해 다음과 같이 수정했다.

from collections import deque
def solution(numbers, target):
    answer = 0
    q = deque()
    n = len(numbers)
    q.append([numbers[0],0])
    q.append([-(numbers[0]), 0])
    while q:
        num, index = q.popleft()
        index += 1
        if index != n:
            q.append([num + numbers[index], index])
            q.append([num - numbers[index], index])
        else:
            if num == target:
                answer += 1
    return answer