[알고리즘] - 프로그래머스(두 개 뽑아서 더하기)

문제설명

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

제한사항

1. numbers의 길이는 2 이상 100 이하입니다.
2. 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 해야 합니다.

나의 풀이

이중 for문을 돌면서 if를 통해 변수에 값이 없고, 인덱스 값이 서로 다르면 값을 저장시키는 식으로 풀어냈다. 그러나 시간복잡도적으로 너무 많이 걸려 list가 아닌 set을 통해 풀었더니 시간이 얼마 걸리지 않았다. 내가 보기에는 이 문제는 set를 통해 풀어야 가장 좋은 방법이나 itertools에 combination을 통해 풀어도 바로 풀리긴 한다 그러나 너무 뭔가 쉽게 풀리는 감이 있어서 나는 이중 for을 통해 풀었다.

2중 for문 구현(list)

def solution(numbers):
    other_numbers=list()
    for i in range(len(numbers)):
        for j in range(len(numbers)):
            if numbers[i]+numbers[j] not in other_numbers and i != j:
                other_numbers.append(numbers[i]+numbers[j])
    other_numbers.sort()
    return list(other_numbers)

실행결과

결과를 보면 테스트7번이 너무 오래걸리는 것을 확인할 수 있습니다. 오래걸리는 이유가 if문에서 not in 이 부분인것 같아서 set로 수정하기로 했습니다. 이유는 list not in은 O(n)이 걸리지만 set not in은 O(1)로 훨씬 빠르기 때문입니다.

2중 for문 구현(set)

def solution(numbers):
    other_numbers = set()
    for i in range(len(numbers)):
        for j in range(len(numbers)):
            if numbers[i]+numbers[j] not in other_numbers and i != j:
                other_numbers.add(numbers[i]+numbers[j])
    other_numbers = sorted(other_numbers)
    return list(other_numbers)

실행결과

보시면 아시겠지만 위와 비교했을 때 가장 오래걸렸던 test7번이 10배나 감소하는 것을 확인할 수 있습니다.

이번에는 한번 itertools combinations를 통해 풀어보겠습니다.

itertools combinations

from itertools import combinations
def solution(numbers):
    return sorted(list(set([sum([i,j]) for i,j in combinations(numbers,2)])))

실행결과

시간복잡도를 보면 set보다 더 오래 걸린다 그렇기에 itertools combinations가 정말 편리하지만 코딩테스트를 볼 때 사용하면 시간초과가 될 확률이 높은 편이다. 그렇기에 사실 편하긴 한데 많이 사용되지는 않는다.