[프로그래머스] LEVEL2 - 타겟넘버(Python)

 

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

코딩테스트 연습 - 타겟 넘버

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

answer

풀이 1

def solution(numbers, target):
    answer = 0
    queue = [[numbers[0],0], [-1*numbers[0],0]]
    n = len(numbers)
    while queue:
        temp, idx = queue.pop()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

print(solution([1, 1, 1, 1, 1], 3))

풀이 2

# 위의 코드보다 효율적인 풀이
def solution(numbers, target):
    result_list = [0] # 초기값 설정
    for number in numbers:
        sub_list = [] # 자식 노드를 생성하기 위한 빈 리스트
        for list_num in result_list: # 노드 하나하나에 더하고 뺸 값을 더하기 위한 반복문
            sub_list.append(list_num + number) # + 한 경우
            sub_list.append(list_num - number) # - 한 경우
        result_list = sub_list # 다음 숫자를 더하고 뺴기 위해 result_list에 sub_list를 대입
    answer = result_list.count(target) # 모든 경우의 수가 있는 result_list에서 타겟넘버의 개수 확인
    return answer

# 테스트 케이스
print(solution([1, 1, 1, 1, 1], 3))

문제를 처음 봤을 때 도무지 풀이가 떠오르지 않아 다른 사람 풀이를 보고 주석이나 달아야겠다 라는 생각으로 코드를 가져오고 분석했으나 추석 전에 작성했던 주석이 어디론가 사라져 있었다.

블로그에 올리기 전 주석을 달아보려 했으나 너무 놀았던 탓인지 코드가 읽히지 않아 주석은 포기하고 조금 더 효율적인 코드가 있는지 찾아봤는데 풀이 2의 코드를 발견했다.

풀이 1의 코드보다 속도는 줄었으니 조금더 효율적인게 맞겠지..?

---

요즘 알고리즘 문제를 풀수록 내 공부방법이 비효율적이라는 생각이 들어 방법을 좀 바꿔보려 한다.

그동안은 문제를 보고 해결방법이 떠오르지 않아도 '하루정도는 직접 풀어보고 안되면 그때 다른 사람 코드를 참고하자'라는 생각을 갖고 공부했었는데 30분 정도 문제를 풀어보고 손도 못 대겠다 싶으면 바로 다른 사람의 코드를 찾아보고 주석을 달며 코드를 분석하는 형태로 바꿔보고자 한다.

이 방법이 좋은 방법인지는 모르겠으나 기존보다 시간도 절약되고 이렇게 하면 더 많은 문제를 접할수 있으니 좋지 않을까 하고 생각한다.

 

ps. 혹시나 알고리즘을 어떻게 공부하면 좋은지 아시는분이 있다면 댓글 부탁드립니다.