[배열과 연결리스트와 덱] -두수의 합-

두 수의 합

정수 수열 안에서 수열의 원소 두 개의 합이 target값이 되는 경우를 찾고 싶습니다.
매개변수 nums에 길이가 n인 수열이 주어지고, 매개변수 target에 자연수 값이 주어지면

이 수열안에서 두 개의 원소의 합이 정수 target값이 되는 두 원소를 구해 배열에 오름차순으로 담아 반환합니다.
두 개의 원소의 합이 target값이 되는 경우는 오직 한가지 뿐인 입력만 주어집니다. 한 원소를 두 번 더하는 것은 안됩니다.

nums의 각 원소는 유일값입니다.
답이 없을 경우 [0, 0]을 반환합니다.

 

제한사항:
• nums의 길이 3 <= n <= 10,000
• 배열 nums의 원소는 정수입니다. -10,000 <= nums[i] <= 10,000 • -20,000 <= target <= 20,000

 

 

 

나의코드 

def solution(nums, target):
    answer = [0] * 2
    for x in nums:
        for y in nums:
            if x+y==target:
                answer[0]=x
                answer[1]=y
    answer.sort()

    return answer

직관적으로 바로 떠오른 2중포문을 사용하였다.

nums의 길이가 최대 10,000개 이니 O(N^2)로 코드를 작성해도 문제가 없다.

 

 

 

정답코드

def solution(nums, target):
    answer = [0] * 2
    n = len(nums)
    for i in range(n-1):
        for j in range(i+1, n):
            if nums[i] + nums[j] == target:
                return sorted([nums[i], nums[j]])
    return answer
        
                                       
print(solution([7, 9, 2, 13, 3, 15, 8, 11], 12))
print(solution([21, 12, 30, 15, 6, 2, 9, 19, 14], 24))
print(solution([12, 18, 5, 8, 21, 27, 22, 25, 16, 2], 28))
print(solution([11, 17, 6, 8, 21, 9, 19, 12, 25, 16, 2], 26))
print(solution([7, 5, 12, -9, -12, 22, -30, -35, -21], -14))
print(solution([7, 5, 12, 20], 15))

흠 정답코드에는 더 획기적인 풀이가 있을줄 알았지만 아니었다..ㅇㅅㅇ.. 

같이 2중 포문이었지만 그래도 내부 반복문에서 순서를 i+1로 시작한점은 기억해야겠다.

 

+아래의 링크와 같이 해시를 사용해서 O(N), 정렬을 사용해서 O(NlogN)으로 해결 할 수 있다.

https://softmoca.tistory.com/19

[해시] - 두 수의 합

 

https://softmoca.tistory.com/29

[정렬] - 두수의 합