파이썬(Python) 알고리즘 문제풀이 두 개 뽑아서 더하기 [프로그래머스 / 정렬]

출처) 프로그래머스 Facebook

from itertools import combinations

def solution(numbers):

    # 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아라
    answer = []

    for unit in list(combinations(numbers, 2)):
        x, y = unit
        sum = x + y
        if sum not in answer:
            answer.append(sum)

    answer = sorted(answer)

    return answer


print(solution([2,1,3,4,1]))
print(solution([5,0,2,7]))

문제 설명

정수 배열 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 해야 합니다.

 

 

풀이 코드

itertools 의 combinations 을 사용할 줄 알면 어렵지 않은 문제. (1,2) 이나 (2,1) 나 같은 걸로 취급하기 떄문에 permutations 이 아닌 combinations 를 사용했다. (1 + 2 == 2 + 1) 니까.

numbers 리스트 길이는 100 이하이므로 나올 수 있는 경우의 수를 nCr 로 계산하면 4,950 개의 경우의 수를 뽑아낼 수 있기 때문에 시간 복잡도도 크게 신경쓰지 않아도 된다고 생각했다.

from itertools import combinations

def solution(numbers):

    # 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아라
    answer = []

    for unit in list(combinations(numbers, 2)):
        x, y = unit
        sum = x + y
        if sum not in answer:
            answer.append(sum)

    answer = sorted(answer)

    return answer


print(solution([2,1,3,4,1]))
print(solution([5,0,2,7]))