프로그래머스 타겟넘버 python, BFS로 풀기

1. 문제

 

2. 설계

dfs와 bfs 둘 다 사용 가능

 

3. 알고리즘

dfs

bfs

queue

memo

 

4. 구현

먼저 조금 더 익숙한 BFS로 다음과 같이 짰다.

1)

- tuple 대신에 list 형태로 append해도 괜찮다.

- while q:

- +1 -1이 아니라 numbers에서 idx만큼 빼와야함.

- append를 +1 -1 둘 다 해야 함

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

 

위의 부분을 다 고쳤더니 index에러가 남.

여기서 딱 한 줄만 고치면 예시 케이스를 통과한다. (#에 써놓음)

def solution(numbers, target):
    answer = 0
    idx =0
    q = []
    q.append([numbers[idx],idx])
    q.append([-1*numbers[idx],idx])
    while q: # while !q.empty()
        cur = q.pop(0)
        if cur[1] != (len(numbers)-1):
        # 여기에 idx = cur[1]를 넣어주면 예시케이스를 통과한다.
            idx+=1
            q.append([cur[0]+numbers[idx], idx])
            q.append([cur[0]-numbers[idx], idx])
        else:
            if cur[0] == target:
                answer+=1
        
    return answer

위의 문제를 수정하면 아래와 같이 되는데 제출하면 첫 두 개를 틀린다.

너무 느려서.

그래서 deque 라이브러리를 사용해야한다.

def solution(numbers, target):
    answer = 0
    idx =0
    q = []
    q.append([numbers[idx],idx])
    q.append([-1*numbers[idx],idx])
    while q: # while !q.empty()
        # print(q)
        cur = q.pop(0)
        idx = cur[1]
        idx+=1
        if idx < len(numbers):
            q.append([cur[0]+numbers[idx], idx])
            q.append([cur[0]-numbers[idx], idx])
        else:
            if cur[0] == target:
                answer+=1
    return answer

 

deque를 사용하는 코드로 만들면 다음과 같고 통과를 한다!

from collections import deque

def solution(numbers, target):
    answer = 0
    idx =0
    q = deque()
    q.append([numbers[idx],idx])
    q.append([-1*numbers[idx],idx])
    
    while q: # while !q.empty()
        # print(q)
        cur = q.popleft()
        idx = cur[1]
        idx+=1
        if idx < len(numbers):
            q.append([cur[0]+numbers[idx], idx])
            q.append([cur[0]-numbers[idx], idx])
        else:
            if cur[0] == target:
                answer+=1
    return answer