코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
두수의 합
앞서 시간복잡도에 대해 학습했으니 시간복잡도를 고려해 다양하게 두 수의 합 문제를 풀어보겠다.
문제
정수 수열 안에서 수열의 원소 두 개의 합이 target값이 되는 경우를 찾고 싶습니다.
매개변수 nums에 길이가 n인 수열이 주어지고, 매개변수 target에 자연수 값이 주어지면 이 수열안에서 두 개의 원소의 합이 정수 target값이 되는 두 원소를 구해 배열에 오름차순으로 담아 반환합니다.
두 개의 원소의 합이 target값이 되는 경우는 오직 한가지 뿐인 입력만 주어집니다. 한 원소를 두 번 더하는 것은 안됩니다. nums의 각 원소는 유일값입니다.
답이 없을 경우 [0, 0]을 반환합니다.
입출력 예
| 입력(nums) | 합(target) | 출력(answer) |
|---|---|---|
| [7, 3, 2, 13, 9, 15, 8, 11] | 12 | [3, 9] |
| [21, 12, 30, 15, 6, 2, 9, 19, 14] | 24 | [9, 15] |
| [12, 18, 5, 8, 21, 27, 22, 25, 16, 2] | 28 | [12, 16] |
| [11, 17, 6, 8, 21, 9, 19, 12, 25, 16, 2] | 26 | [9, 17] |
| [7, 5, 12, -9, -12, 22, -30, -35, -21] | -14 | [-21, 7] |
| [7, 5, 12, 20] | 15 | [0, 0] |
제한사항
- nums의 길이 3 <= n <= 10,000
- 배열 nums의 원소는 정수입니다. -10,000 <= nums[i] <= 10,000
- -20,000 <= target <= 20,000
시간복잡도(n²)
def solution(nums, target):
n = len(nums)
for i in range(n):
for j in range(n):
if nums[i] + nums[j] == target:
return sorted([nums[i], nums[j]])
return [0, 0]
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))
중첩 for문으로 구현해 시간복잡도는 O(n²)이다.
시간복잡도(nlogn)
def solution(nums, target):
nums.sort()
nH = {}
for i in nums:
if (target - i) in nH:
return[target - i, i]
else:
nH[i] = 1
return [0, 0]
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))
사전형으로 구현했고, 정렬으로 인해 시간복잡도는 O(nlogn)이다.
- 앞서 정렬을 했기 때문에
return [target -i, i]할 때 따로 정렬할 필요 없음 nH[i]: 해당x값이 존재한다는 표시
시간복잡도(n)
from collections import defaultdict
def solution(nums, target):
nH = defaultdict(int)
for x in nums:
y = target - x
if y in nH:
return sorted([x, y])
nH[x] = 1
return [0, 0]
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))
defaultdict(인자) :
value를 지정하지 않은 모든key의value를인자의 자료형으로 가짐
따라서 최초에 없는key값을 입력해도 에러가 나지 않고, 설정된 자료형으로 모든value초기화
nH에defaultdict(int)를 이용해 모든key값을0으로 초기화x + y = target이라고 했을 때y = target - x도 만족target - x를 만족하는y가- 있는 경우 :
return sorted([x, y]) - 없는 경우 : 해당
x값이 존재한다는 표시로nH[x] = 1
- 있는 경우 :
- 그렇게 원소를 돌다가
target - x를 만족하는y를 찾지 못했다면return [0, 0]
끄적끄적