프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
from collections import deque
def solution(numbers, target):
answer = 0
q = deque([(0, -1)])
while q:
now, idx = q.popleft()
if idx + 1 == len(numbers):
if now == target:
answer += 1
continue
for i in [numbers[idx+1], numbers[idx+1]*(-1)]:
q.append((now+i, idx+1))
return answer
나는 BFS를 이용하여 풀이해보았다.
deque에 (계산값, 인덱스)를 튜플로 묶어서 넣어서 popleft로 하나씩 뽑아가며 확인을 한다. 처음에는 (0, -1)을 넣어준다.
numbers 배열의 끝에 도달할 때까지 큐에 현재값에서 배열의 (현재 인덱스+1) 값을 더하거나 빼준 값과 (현재 인덱스+1) 값을 튜플로 넣어준다. 배열의 끝에 도달했는데 현재값이 target과 같다면 타겟 넘버를 만들 수 있는 조합이었다는 뜻이므로 answer 값을 증가시켜주고 그 다음의 코드들은 더이상 실행하지 않고 다시 while문의 처음으로 가도록 continue해준다.
다 풀고 다른 사람들의 풀이를 봤는데 진짜 이건 다양한 풀이가 많았다. 나는 BFS를 이용했지만 재귀를 이용한 DFS로 푼 사람들이 많은 것 같았다. 그 중 인상깊었던 건 바로 다음 코드였다.
def solution(numbers, target):
if not numbers and target == 0 :
return 1
elif not numbers:
return 0
else:
return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])
간결하고 깔끔하기도 한데 이해하기에도 어렵지 않은 코드였다.
어차피 numbers의 순서는 변하지 않는다는 조건이 있으니 가장 첫번째 번호만 target에서 빼거나 더해주고 2번째 번호부터는 solution 함수에 첫번째 인자로 넘겨준다. 쉽게 말하자면 배열의 가장 첫번째 원소를 pop해서 target에서 빼거나 더해주고 남은 배열만 넘겨줬다는 말이다. 이렇게 계속 재귀적으로 가다가 numbers 배열이 빈다면 리턴해줄건데 target이 0이 되었다면 원하는 타겟넘버를 만들 수 있었다는 말이므로 1을 리턴해주고 그렇지 않다면 0을 리턴해주는 코드이다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 15591번 MooTube (Silver) (0) | 2023.01.07 |
---|---|
[Python/파이썬] 프로그래머스 피로도 (0) | 2022.12.19 |
[Python/파이썬] 프로그래머스 단어 변환 (0) | 2022.10.21 |
[Python/파이썬] 프로그래머스 네트워크 (0) | 2022.10.14 |
[Python/파이썬] 2022 KAKAO BLIND RECRUITMENT 양궁대회 (0) | 2022.10.12 |