[Python] 코드잇 : 리스트 항목 합 탐색, Brute Force

 

 

📝 문제

[1, 2, 5, 6, 7, 9, 11] 안에 합이 15가 되는 두 요소의 조합이 있는지 확인하고 싶습니다. 두 요소 6과 9의 합이 15가 되죠? 이 조합이 있는지 없는지를 알고 싶은 거죠.

함수 sum_in_list()는 정수 search_sum과 정렬된 정수 리스트 sorted_list를 받아서 sorted_list안의 두 요소의 합이 search_sum이 되는 조합이 있는지 없는지를 불린으로 리턴합니다.

sum_in_list(15, [1, 2, 5, 6, 7, 9, 11])은 불린 True를 리턴합니다.

 

🫠 나의 풀이, 브루트 포스 O(n2)

def sum_in_list(search_sum, sorted_list):
    for i in range(len(sorted_list)):
        for j in range(i, len(sorted_list)):
            if sorted_list[i] + sorted_list[j] == search_sum:
                return True
    return False

 

🧞‍♂️ 시간 복잡도를 줄인 풀이 O(n)

def sum_in_list(search_sum, sorted_list):
    low = 0
    high = len(sorted_list) - 1
    
    while low < high:
        total = sorted_list[low] + sorted_list[high]
        
        if total == search_sum:
            return True
        
        if total < search_sum:
            low += 1
        
        else:
            high -= 1
    
    return False


print(sum_in_list(15, [1, 2, 5, 6, 7, 9, 11]))
print(sum_in_list(15, [1, 2, 5, 7, 9, 11]))

 

 

 

🔗 https://www.codeit.kr/topics/practicing-algorithmic-problem-solving/lessons/1566

리스트 항목 합 탐색 - 문제 해결 능력 기르기 | 코드잇