문제
- Int 타입 배열
nums와 int 타입target이 주어진다. nums배열 중 두 개의 수를 합하여target과 일치하는 두 index를 배열로 반환해야 한다.- 문제에서는 오직 오직 하나의 Output이 나옴을 보장하고 있다.
예시 1
- Input : nums = [2, 7, 11, 15], target = 9
- output : [0, 1]
- nums[0] + nums[1] == 9, 따라서 [0, 1] 이 리턴됨.
예시 2
- input : nums = [3, 2, 4], target = 6
- output : [1, 2]
예시 3
- input : nums = [3, 3], target = 6
- output : [0, 1]
제약사항
- 2 <= nums.length <= 103
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 오직 하나의 정답만 존재한다.
풀이 1. Brute force
일단 브루탈포스로 이중 for문을 돌며 체크하는 방법으로 진행했다.
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var result: [Int] = []
for i in 0...nums.count-1 {
if i != nums.count-1 {
for j in i+1...nums.count-1 {
if nums[i]+nums[j] == target {
result.append(i)
result.append(j)
}
}
}
}
return result
}
}
[결과]
Runtime 이 72ms 가 나왔다. 해결 자체는 가능하지만 이중 for문을 사용하기 때문에 O(n^2) 의 시간이 걸려 그리 효율적이진 못하다.
풀이 2. Dictionary 이용
좀 더 효율적으로 해결할 순 없을까?
leetCode에서는 자체적으로 솔루션을 제공해준다. (나같은 알고리즘알못에겐 고마운 기능이다)
일단 현재 index와 다음 index를 체크하는 이중 포문 로직을 효율적으로 변경해보자.
- 먼저 Dictonary에
[nums[i] : i]형태로 저장한다. - 이후 nums를 돌며
target - 현재 nums[i]의 값이 Dictionary의 key로 들어가 있는지 확인한다. - 있다면 해당 key에 저장된 value 값 (index)를 뽑아내 이전 i 값과 함께 결과값으로 리턴한다.
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var result: [Int] = []
var dic: [Int : Int] = [:]
// Dictionary에 value : index 형태로 저장
for i in 0...nums.count-1 {
dic[nums[i]] = i
}
// nums 를 돌며 체크
for i in 0...nums.count-1 {
let check = target - nums[i]
// dictionary key에 check 값이 있는지 확인하고, 있을 경우 key에 해당하는 value값이 현재 index가 아니라면 정답이므로 해당 index들을 저장한다.
if let j = dic[check], j != i {
result.append(i)
result.append(j)
break;
}
}
return result
}
}[결과]
Runtime 이 32ms 로 약 절반가량 줄었다. 이는 dictionary 조회 시 O(1)의 시간복잡도를 가지고 있기 때문에, 시간복잡도도 최악의 경우에 nums의 count만큼 돌기 때문에 O(n)이다. 기존 O(n2)던 것에 비해 많이 줄었다.
하지만 공간 복잡도가 Dictionary를 사용함에 따라 기존 브루탈포스 O(1) -> O(n)으로 늘었다. (뭐.. 공간 복잡도는 시간복잡도에 비해 상대적으로 중요하지 않기 때문에,크게 신경쓰지 않아도 된다.)
풀이 3. 더욱 간결하게
앞서 풀이 2 에서는 Dictionary를 세팅한 다음, input 배열을 돌며 체크를 하는 방식인데, 이 때 체크하는 Dictionary의 value(index) 값이 현재 배열의 index값과 같은지 체크를 해야 한다. (물론 옵셔널 바인딩할 때 같이 체크를 하지만.. 굳이 체크할 필요가 없다면 더 좋지 않을까?)
Dictionary의 세팅하는 과정을 nums 배열을 탐색하며 같이 진행한다면? 아래와 같이 진행해 볼 수 있을 것이다. (leetCode 의 솔루션에서는 One-pass Hash Table 이라는 이름으로 소개하고 있다.)
- 먼저 nums 배열을 탐색하며
target - nums[i]의 값이 Dictionary의 key에 등록되어 있는지 확인한다. - 만약 없다면 현재 인덱스에 대해
[nums[i] : i]의 형태로 Dictionary에 저장한다. - 만약 있다면 현재 배열 인덱스와 Dictionary에서 일치한 index value 값이 정답이다.
이를 위 예시 1 을 예시로 한번 확인해보자면,
| i | nums[I] | target - nums[I] | Dictionary | 비고 |
|---|---|---|---|---|
| 0 | 3 | 6 - 3 = 3 | [ ] | 일치하는 값이 Dictionary에 없으므로 Dictionary에 [3:0] 등록 |
| 1 | 2 | 6 - 2 = 4 | [[3:0]] | 일치하는 값이 Dictionary에 없으므로 Dictionary에 [2:1] 등록 |
| 2 | 4 | 6 - 4 = 2 | [[3:0],[2:1]] | Dictionary에 일치하는 값 [2:1] 이 있으므로 정답. 결과값은 [1, 2] |
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var result: [Int] = []
var dic: [Int : Int] = [:]
for i in 0...nums.count-1 {
let check = target - nums[i]
// 옵셔널 바인딩으로 dictionary 확인
if let j = dic[check] {
// 있다면 답이므로 결과값 세팅
// * 이렇게 짤 경우 결과값이 내림차순 식으로 세팅되는데, leetCode 상에서 문제는 없다고 판단하나 보다. 결과값은 소팅되지 않아도 되는듯..
result.append(i)
result.append(j)
break;
}
// dictionary에 없다면 현재 index값에 대해 넣어준다.
dic[nums[i]] = i
}
return result
}
}[결과]
풀이 2 와 비슷한 결과가 나온다. 이 역시 결국 num 배열을 한번 순회해야 하므로 최악의 경우 시간복잡도는 `O(n) 가 나온다.
정리
문제 자체는 단순한 문제지만, 예전에는 브루탈포스로 해결하기만 급급했다면 이번 문제를 풀면서 순회탐색을 이용한 문제풀이 시 Dictionary (Map) 으로 해결하는 방법을 이해하게 된 것 같다.
단순히 코딩 테스트를 연습하는 마음으로 시작하는 첫 포스팅이지만, 이번 문제를 풀며 나 스스로도 문제 해결을 위한 사고의 폭이 넓혀지는 듯 하다.
앞으로도 꾸준히 문제를 풀면서 이번과 같이 정리를 해야겠다 싶다. (여러 다양한 문제 풀이 방법을 봐야 이후 다른 문제에서도 응용할 수 있을테니까..)
