2번 문제 역시 스스로 해결했다! 신난다!
프로그래머스 레벨 2 문제다!
타겟 넘버
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
문제를 이해하는게 조금 어려웠지만, 배운 것을 사용해서 멋지게 풀어내는데 성공했다!
문제포인트 1 : 정수들을 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만드는 방법의 수!
경우의 수 구하는 문제다! 다만 양수가 아닌 음수도 있어서 경우의 수가 많아지는 문제다!
문제포인트 2 : 타겟 넘버 하나만 구하면 된다! 리스트 안에서 문자열이든 정수든 뭐든 찾아서 그 갯수를 리턴해주는 count 함수를 쓸 때가 온 것 같다! 리스트함수 열심히 적어두길 잘했다!
문제포인트 3 : 제한사항에 따른 타임아웃을 주의해야 한다!
- 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
- 각 숫자는 1 이상 50 이하인 자연수입니다.
- 타겟 넘버는 1 이상 1000 이하인 자연수입니다.
전체 코드
def solution(numbers, target):
main = [0]
for i in numbers:
force = []
for j in main:
force.append(j+i)
force.append(j-i)
main = force
# print(main)
return main.count(target)시험 전날 스터디에서 배웠던 이중for문으로 풀고 싶어서 열심히 고민해본 결과,
비록 조금 무겁지만 무척이나 간결하고 이쁜 코드가 나왔다!
이중for문, 다중for문은 포문을 여러개 겹쳐서 바깥쪽 for문에 있는 변수와 안쪽 for문에 있는 변수를
더할 수 있게 해주는 멋진 알고리즘 스킬이다. 구구단을 자동으로 뽑거나, 별로 양탄자를 찍거나
그리고 어떤 범위 내의 모든 경우의 수를 구할때 쓰인다!
그래서 구상한 알고리즘 순서
- 이중포문으로 발생할 수 있는 모든 경우의 수를 일단 다 담는다.
- 배열에 count 함수를 적용하여 값이 target인게 몇개나 있는지 세어 리턴한다!
당연하게도 타임아웃이 나왔다.
그래서 이래저래 구글링을 통해 알아낸 방법!
inner for문 안에서 main을 걸어서 j+i를 양수로 한번, 음수로 한번씩 추가해준다.
이때 main에 직접 추가해주는게 아니라 force라는 빈 배열을 하나 담아서 거기에 append해준다.
main 배열의 길이는 1이지만 얘는 i값을 담는 용도고
어차피 바깥 for문은 계속 돌고 있기 때문에 내부 배열에는 정상적으로 스택이 쌓인다.
j값이 i 안에서 계속 돌아가면서 i로 가능한 모든 수를 담는다.
주의해야 할 점! 이 배열은 inner for문에서만 사용되고 사라지기 때문에,
사라지기 전에 재빨리 main배열에 참조를 할당해주어야 한다.
그리고 main에 target을 인자로 받는 count함수를 리턴해주면 끝!
엄청 긴 길이의 배열이라면 이 방법이 안통하겠지만, 다행히 문제는 길어야 20개 치 길이의 정수다.
그래도 이제 문제를 내 힘으로 풀 수 있다! 예압!
