Algorithm / 두 개 뽑아서 더하기

문제 설명

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

정답 제출

func solution(_ numbers:[Int]) -> [Int] {
    var answer: [Int] = []
    var visitNum: Set<Int> = []
    var numDic: [Int: [Int]] = [:]
    
    for (i, j) in numbers.enumerated() {
        let key = j
        var values = numbers
        values.remove(at: i)
        
        numDic[key, default: []].append(contentsOf: values)
    }
    
    numDic.forEach { dic in
        for i in dic.value {
            let num = dic.key + i
            visitNum.insert(num)
        }
    }
    
    answer = Array(visitNum).sorted()
    
    return answer
}

결과-1

성능 개선

기존에 제출한 코드는 불필요한 코드가 많고, 성능 저하나 시간 복잡도 문제가 있다고 생각하여 다시 개선하여 코드를 제출하였다.

1. numDic 제거 -> 메모리 절약
2. remove(at:)제거 -> 성능 개선
3. 반복문 범위 최적화
4. 정렬 후 반환

func solution(_ numbers: [Int]) -> [Int] {
    var visitNum = Set<Int>()  // 중복 제거를 위한 Set 사용
    
    let count = numbers.count
    for i in 0..<count {
        for j in i+1..<count { // 중복 방지를 위해 j를 i+1부터 시작
            visitNum.insert(numbers[i] + numbers[j])
        }
    }
    
    return Array(visitNum).sorted()
}

결과-2