[프로그래머스] 두개 뽑아서 더하기 [월간 코드 챌린지 시즌1][python]

<프로그래머스> 두개 뽑아서 더하기 <월간 코드 챌린지 시즌 1> <python>

 

중복x, 모든 조합 을 생각하고 접근하면 쉽게 해결 할 수 있는 문제이다.

 

 

문제 설명

 

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

 

입출력 예 #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 해야 합니다.

설계 및 구현

 

my_solution1

 

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        for j in range(i+1,len(numbers)):
            if (numbers[j] + numbers[i]) not in answer:
                answer.append(numbers[j] + numbers[i])
    return sorted(answer)

1. 이중 for문을 돌려 모든 요소에 이중 접근해서 solutins을 작성하였다.

for i in range(len(numbers):

    for j in range(i+1,len(numbers)):

이런식으로 모든 서로다른 두개요소의 합을 구하였고 if문으로 중복이 일어나지 않게 구현하였다.

2.sorted() 를 이용해 정렬 하여 반환하여 해결 하였다.

 

하지만 너무 파이써닉하지 못한 solution이라 생각해서 좀더 파이써닉하게 수정 하였다.

 

 

my_solution2

from itertools import combinations

def solution(numbers):
    answer = set()
    for i in list(combinations(numbers,2)):
        answer.add(sum(i))
    return sorted(answer)

1. 리스트 조합의 결과를 반환하는 함수 combinations를 사용하였다.

2. combinations(numbers,2)은 numbers의 2개의 요소로 구할 수 있는 모든 조합을 반환한다.

3. 중복을 피하기 위해 answer은 set()로 초기화한다.

4. answer.add(sum(i)) 를 통해 모든 조합의 합을 중복없이 answer에 쌓을 수 있다.

5. 마지막으로 정렬을 한뒤 반환한다.

 

my_solution2

 

 

두개의 solution의 시간복잡도를 비교해보면

파이썬이 내장함수가 최적화가 잘 되 있다보니 

 

두 가지 solution 비교

my_solution1 vs my_solution2 시간 복잡도 비교

전체적으로 비슷하지만 테스트 6,7,9를 보면 모든 요소에 이중 for문으로 접근했던 my_solution1이 성능이 떨어지는 모습을 볼 수 있다.

조합을 구할때 파이썬의 내장함수 인 combinations()를 썻는데 파이썬의 내장함수가 최적화가 잘 되있다보니

모든 요소에 이중 for문으로 접근했던 my_solution1에 비해 my_solution2가 뛰어난 성능을 보여준다.

 

 

다른 분의 모범 solution

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            answer.append(numbers[i] + numbers[j])
    return sorted(list(set(answer)))

 

from itertools import combinations




def solution(numbers):
    answer = []
    l = list(combinations(numbers, 2))

    for i in l:
        answer.append(i[0]+i[1])
    answer = list(set(answer))
    answer.sort()

    return answer