Notice
Recent Posts
Recent Comments
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

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

프로그래밍

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

yesungcho 2022. 1. 29. 19:36

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

 

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

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

programmers.co.kr

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