코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- 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] |
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²)이다.
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
값이 존재한다는 표시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]