문제 설명
정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
-
numbers의 길이는 2 이상 100 이하입니다.
-> numbers의 모든 수는 0 이상 100 이하입니다.
입출력 예
| numbers | result |
|---|---|
[2,1,3,4,1] | [2,3,4,5,6,7] |
[5,0,2,7] | [2,5,7,9,12] |
입출력 예 설명
입출력 예 #1
- 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.)
- 3 = 2 + 1 입니다.
- 4 = 1 + 3 입니다.
- 5 = 1 + 4 = 2 + 3 입니다.
- 6 = 2 + 4 입니다.
- 7 = 3 + 4 입니다.
- 따라서
[2,3,4,5,6,7]을 return 해야 합니다.
입출력 예 #2
- 2 = 0 + 2 입니다.
- 5 = 5 + 0 입니다.
- 7 = 0 + 7 = 5 + 2 입니다.
- 9 = 2 + 7 입니다.
- 12 = 5 + 7 입니다.
- 따라서
[2,5,7,9,12]를 return 해야 합니다.
내 문제 풀이
- 고등학교때 배운 조합을 생각 해보자. 예를 들어서 입력이 #1 처럼
[2,1,3,4,1]로 들어왔다고 가정하자.
-> 두 개 뽑아서 더하는 문제니 두 개를 뽑을 수 있는 방법인 조합을 생각 해 보면 다음과 같다.
(1) 2 (1번째 인덱스)를 뽑았을 때 더할 수 있는 경우 : 4가지 (1,3,4,1)
(2) 1 (2번째 인덱스)를 뽑았을 때 더할 수 있는 경우 : 3가지 (3,4,1 - 첫 번째 인덱스 값인 2와는 (1)에서 더했으니까 더할 필요가 없다)
(3) 3 (3번째 인덱스)를 뽑았을 때 더할 수 있는 경우 : 2가지 (4,1)
(4) 4 (4번째 인덱스)를 뽑았을 때 더할 수 있는 경우 : 1가지 (1)
(5) 1 (5번째 인덱스)를 뽑았을 떄 더할 수 있는 경우 : 0가지 (이미 앞의 4번쨰 횟수를 통해 모두 더했음을 알 수 있다)
이를 통해 알 수 있는 사실은 5개 원소에서 2개 뽑는 방법은 10가지 임을 알 수 있다. 이를 일반화 하자면 아래 그림과 같다.
(출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=vollollov&logNo=220915481071)
-
위 내용을 구현하기 위해 반복문은 2개를 써야한다.
-
첫 번째 반복문은 위 예시에선 2,1,3,4, 즉 더할 원소 중 첫 번째 값 하나. 이때 마지막 원소인 1(인덱스는 4) 은 뽑을 필요가 없으니까 조건문의 범위를 range(len(numbers))가 아닌 range(len(numbers)-1) 까지 한다.
-
두 번째 반복분은 원소가 하나 뽑혔을 때 더할 수 있는 나머지 숫자를 위한 반복문
-> 예를 들어 첫 번째 반복문에서 첫 번째 인덱스의 값인 2가 뽑혔을 때 두 번쨰 반복문에서 나올 수 있는 케이스는 4개 (두 번째~다섯 번쨰 인덱스의 값) 이다. 이를 통해 알 수 있는건 두 번째 반복문의 시작은 첫 번째 반복문의 시작 보다 바로 한 칸 뒤에서 시작 해야 한다. 따라서 반복문의 범위는 range(i+1, range(numbers)) 가 된다.
-
-
이때 더한 결과값을 결과를 출력하는 list에 append 시킨다.
-> 이때 값의 중복이 있을 수 있다. 따라서 더한 값이 list에 있는지 먼저 확인 후 없는 경우에만 추가한다. -
추가하고 나선 sort() 함수를 이용하여 결과를 출력하는 list를 정렬한다.
def solution(numbers):
l = []
for i in range(len(numbers)-1):
for j in range(i+1,len(numbers)):
if numbers[i]+numbers[j] in l:
continue
else:
l.append(numbers[i]+numbers[j])
l.sort()
return l부족한 점
- sort를 리스트에 append 하지 않고 한 번만 거치면 성능적으론 좋았을 것 같다. (
return sorted(l)) - 중복 저장을 허용 하지 않는 set도 생각 했는데 이번엔 list 만으로 풀고 싶어서 set를 안 썼다.
