[프로그래머스/Day 9] 두 개 뽑아서 더하기 - set STL의 원리, set을 사용하는 이유

1. 서론

다음 코드는 두 개 뽑아서 더하기 문제의 풀이로 작성한 코드다.

의사 코드도 작성하고 그에 맞춰서 단계적으로 풀이했다.

// 1. 중첩 반복문으로 두 수의 합을 더해 set에 추가한다.
// - set은 자동으로 중복이 제거되고 정렬되므로 이 문제에 제격이라 생각됨.
// 2. set에 있는 값을 answer에 추가한다.
// 3. answer를 오름차순 정렬한다.
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    set<int> sumSet;
    const size_t NUMBERS_SIZE = numbers.size();

    // 1. 중첩 반복문으로 두 수의 합을 더해 set에 추가한다.
    for(size_t t1 = 0; t1 < NUMBERS_SIZE; ++t1)
    {
        for(size_t t2 = t1 + 1; t2 < NUMBERS_SIZE; ++t2)
        {
            sumSet.insert(numbers[t1] + numbers[t2]);
        }
    }

    // 2. set에 있는 값을 answer에 추가한다.
    for(int sumNumber : sumSet)
    {
        answer.push_back(sumNumber);
    }

    // 3. answer를 오름차순 정렬한다.
    sort(answer.begin(), answer.end());

    return answer;
}

문제를 풀 때 들었던 생각은 "set을 쓰면 바로 해결할 수 있겠는데? 와 C++ 이 제공하는 STL이니까 성능은 뭐, 좋지 않을까?" 라는 생각에서 온 사용이었다.

중복이 제거되고 오름차순으로 정렬된다고만 알고 있을 뿐 set 내부에서 어떻게 돌아가는지는 전혀 몰랐다.

그 내용을 정리하려고 이 글을 작성한다.

---

2. 본론

2-1. set은 이진 탐색 트리 구조다!

• 이진 탐색 트리의 정렬 규칙
  • 부모 노드보다 작은 값은 무조건 왼쪽 자식으로 보낸다.
  • 부모 노드보다 큰 값은 무조건 오른쪽 자식으로 보낸다.
• 중복 제거 규칙
  • 새로운 값을 넣으려는데 이미 똑같은 값이 트리에 있다면 무시한다.
• 중위 순회를 통해 오름차순 정렬된 결과가 나온다.

2-2. 이진 탐색 트리 중에서도 레드-블랙 트리 구조다!

• 단순히 이진 탐색 트리만 사용하는 경우, 데이터가 1, 2, 3, 4, 5와 같이 순서대로 들어온다면 항상 다음 수가 크므로 트리는 오른쪽으로만 길게 뻗은 Linked List 모양이 되어 탐색 속도가 느려진다.
• 레드-블랙 트리는 데이터가 추가·삭제될 때마다 트리가 한쪽으로 치우치지 않도록, 노드의 색깔을 Red 또는 Black으로 바꾸거나 위치를 Rotation 시켜 트리의 높이를 일정하게 유지한다.
  • 우회전 (Right Rotation): 왼쪽이 너무 무거울 때, 왼쪽 자식을 위로 올리고 부모를 오른쪽 아래로 내림. (갈 곳 잃은 자식은 기존 부모의 왼쪽으로 붙임)
  • 좌회전 (Left Rotation): 오른쪽이 너무 무거울 때, 반대로 수행.
• 그 결과, 어떤 데이터가 들어오더라도 트리의 높이가 너무 높아지지 않도록 방지한다.

2-3. 시간 복잡도와 연결지어 생각해보자!

• 트리 구조에서 데이터를 찾거나 넣으려면 Root에서 시작해서 Leaf까지 내려가야 한다. 즉, 연산의 횟수는 트리의 높이와 비례한다.

2-3-1. 탐색 (Search)

• 값이 부모 노드보다 작으면 왼쪽, 크면 오른쪽으로 한 단계씩 내려간다.
• 한 번 내려갈 때마다 탐색 범위가 절반씩 줄어든다.
• 따라서 데이터가 N개일 때, 트리의 높이는 약 log₂N이 된다.
• 시간 복잡도: O(log N)

 

2-3-2. 삽입 (Insert)

• 들어갈 위치를 찾아야 하므로 탐색과 똑같이 내려간다. O(log N)
• 위치를 찾은 후 노드를 붙이고, 필요하면 트리의 균형을 다시 맞춘다. O(1) 혹은 높이에 비례하는 시간
• 시간 복잡도: O(log N)

2-3-3. 삭제 (Delete)

• 지울 값을 찾는다. O(log N)
• 지운 뒤, 필요하면 트리의 균형을 다시 맞춘다. O(1) 혹은 높이에 비례하는 시간
• 시간 복잡도: O(log N)

---

3. 결론

• set은 새로운 데이터가 들어올 때부터 크기 비교를 통해 자신의 위치를 찾아가 정렬 효과를 볼 수 있다.
• 이미 있는 값이면 트리에 넣지 않아 중복 제거 효과를 볼 수 있다.
• 레드-블랙 트리 알고리즘이 트리의 높이를 조절해 데이터가 아무리 많아도 탐색 경로를 짧게 log N으로 유지한다.
• 그 덕에 데이터가 100만 개 있어도 약 20번의 비교만으로 원하는 값을 찾거나 넣을 수 있다.