No Limitation
[정렬] 두 수 뽑아서 더하기 - 프로그래머스 본문
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
'프로그래밍' 카테고리의 다른 글
[스택큐] 프린터 - 프로그래머스 (0) | 2022.01.29 |
---|---|
[스택큐] 주식 가격 - 프로그래머스 (0) | 2022.01.29 |
[정렬] h-index - 프로그래머스 (0) | 2022.01.29 |
[정렬] 가장 큰 수 - 프로그래머스, 정렬 Customizing (0) | 2022.01.29 |
[정렬] K 번째 수 - 프로그래머스 (0) | 2022.01.29 |