[정렬] 두 수 뽑아서 더하기 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/68644?language=python3 

코딩테스트 연습 - 두 개 뽑아서 더하기

Level1 두 개 뽑아서 더하기 문제

본 문제는 단순하게 for 반복문 2개를 사용하여 계산을 하고 요소가 있는 지 없는 지를 확인해주는 in method까지 사용할 경우 최악의 경우 O(n^3)까지 알고리즘이 증가하는 굉장히 비효율적인 알고리즘이다.

 

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

하지만 이 부분에서 보다 효율적으로 O(n^2)으로 낮출 수 있는 여러 heuristic이 존재를 하는데

list comprehension의 이용과 중복 제거 시 set을 활용하면 어떨까 하는 부분이었다. 하지만 set으로 사용하는 것도 어느 정도 time cost가 드는 지는 명확히 확인이 되지 못했다.

하지만 명확하게 list comprehension을 통해 append에 들어가는 cost를 상당히 많이 줄일 수 있다는 점에서 의미가 있고 또한 코드가 훨씬 가독성이 좋게 변하는 부분을 알 수 있었다.

실제로 테스트 케이스 7번 같이 용량이 큰 데이터의 경우 훨씬 시간이 빨랐음을 알 수 있었다.

 

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