[Algorithm] [Swift] Programmers - 두 개 뽑아서 더하기

두 개 뽑아서 더하기

---

 

문제 설명

---

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

 

제한 사항

---

• numbers의 길이는 2 이상 100 이하입니다.
  • numbers의 모든 수는 0 이상 100 이하입니다.

 

입출력 예

---

• numbers: [2, 1, 3, 4, 1], result: [2, 3, 4, 5, 6, 7]
• numbers: [5, 0, 2, 7], result: [2, 5, 7, 9, 12]

 

제출 코드

---

1차

func solution(_ numbers: [Int]) -> [Int] {
    var answers: [Int] = []

    for i in 0..<numbers.count {
        for j in i+1..<numbers.count {
            if !answer.contains(numbers[i] + numbers[j]) {
                answer.append(numbers[i] + numbers[j])
            }
        }
    }
    return answer.sorted(by: <)
}

 

2차

func solution(_ numbers: [Int]) -> [Int] {
    var answer: Set<Int> = []

    for i in 0..<numbers.count {
        for j in i+1..<numbers.count {
            answer.insert(numbers[i] + numbers[j])
        }
    }
    return Array(answer).sorted(by: <)
}

 

문제 풀이

---

문제는 매우 간단합니다.

 

주어진 배열 numbers에서 index가 다른 두 개의 숫자를 더해 나올 수 있는 모든 경우의 수를 구해내면 됩니다.

 

입력값의 최대 길이가 100 임을 확인하고 O(N!) 복잡도를 갖는 완전탐색을 이용하여 모든 경우의 수를 탐색했습니다.

 

outer_loop의 index를 담당할 i 변수와 inner_loop의 index j를 이용하였으며 불필요한 중복 탐색 제거를 위해 j 인덱스의 시작은 i+1 로 설정하였습니다.

 

처음에는 반환할 정답을 배열 타입으로 선언하고 두 정수의 합이 이미 배열 내에 존재하는가에 따라 분기하였습니다.

 

코드를 제출하고 좀 더 생각해보니 Set 자료구조를 사용하는 것이 더욱 효율적일 것 같은 생각이 들었습니다.

 

Set 자료구조는 자체적으로 중복을 관리하기에 별도 관리를 할 필요가 없고 Set 내 데이터를 삽입하는 insert 메소드 또한 O(1) 복잡도를 갖기에 현재 문제에서 사용하기에 적합한 자료구조라고 생각이 들었..ㅎㅎ

 

따라서 Set을 이용하여 정답을 추려내기 위한 모든 연산을 진행하고 최종 반환값만 배열 타입으로 변환하여 반환하도록 코드를 수정하였습니다.