Lv 0. 배열의 유사도 - 효율적인 검색을 고려한 rb트리를 이용한 풀이. c++에서는 set *다시 풀어보기*

https://school.programmers.co.kr/learn/courses/30/lessons/120903

#include <string>
#include <vector>

using namespace std;

int solution(vector<string> s1, vector<string> s2) {
    int answer = 0;
    for(auto c: s1){
        for(auto s: s2){
            if(c==s) answer++;
        }
    }
    return answer;
}

위의 풀이는 내가 작성한 풀이이고,

다른 사람의 풀이를 보니까 아래와 같은 풀이를 보게 되었다. set을 이용한 풀이이다.

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(vector<string> s1, vector<string> s2) {
    int answer = 0;
    set<string> s3(s1.begin(), s1.end());
    for(int i = 0; i < s2.size(); i ++){
        if(s3.find(s2[i])!=s3.end()){
            answer++;
        }
    }
    return answer;
}

먼저 이 코드에 대해서 제대로 이해하기 위해서는 set에 대해서 알아야 하니까, set에 대해서 한번 검색을 해보면,

---

set에 대한 gpt 답변

C++의 std::set은 정렬된(unique, 중복 없는) 원소들의 컬렉션을 나타내는 컨테이너입니다. std::set은 C++ 표준 라이브러리에서 제공하는 "레드-블랙 트리"라는 데이터 구조를 기반으로 구현되어 있어, 데이터의 삽입, 삭제, 검색 연산을 평균 O(log N)의 시간복잡도로 수행할 수 있습니다.

std::set의 특징과 사용법에 대한 몇 가지 주요한 점을 설명하겠습니다:

1. 정렬된 자동 정렬: std::set은 내부적으로 원소들을 자동으로 정렬합니다. 삽입할 때마다 정렬을 수동으로 처리할 필요가 없습니다.
2. 중복 원소 제거: std::set은 중복된 원소를 허용하지 않습니다. 같은 원소를 여러 번 추가해도 하나의 원소만 저장됩니다.
3. 검색 및 삽입: std::set에서 원소를 검색하거나 추가하는 연산은 빠르게 수행됩니다. 검색은 이진 검색 트리를 사용하여 O(log N) 시간에 이루어집니다.
4. 삽입 및 삭제: 원소를 삽입하거나 삭제할 때, 이진 검색 트리를 유지하기 위해 균형을 잡기 위한 회전 연산을 내부적으로 수행합니다.
5. 반복자 활용: std::set은 반복자(iterator)를 통해 원소를 순회할 수 있습니다. begin()과 end() 함수로 범위를 지정하여 사용할 수 있습니다.
6. 범위 기반 삭제: 특정 범위 내의 원소를 삭제할 때 유용한 함수들을 제공합니다.
7. 원소의 존재 여부 확인: find() 함수를 사용하여 특정 원소의 존재 여부를 확인할 수 있습니다.
8. 컨테이너의 크기: size() 함수를 통해 std::set에 저장된 원소의 개수를 확인할 수 있습니다.
9. 사용자 지정 정렬 기준: std::set은 기본적으로 오름차순으로 원소를 정렬합니다. 원하는 대로 정렬 기준을 변경할 수 있도록 사용자 지정 정렬 함수나 함수 객체를 지정할 수 있습니다.
10. std::set은 중복 없이 원소를 저장하고 정렬된 상태를 유지해야 할 때 유용하게 사용됩니다. 주로 검색과 삽입 연산이 빈번한 경우나 데이터를 유지하면서 정렬된 상태로 관리해야 할 때 사용됩니다.

---

이와 같은 답변을 얻을 수 있었다. 결국에는 위 set으로 입력받아서 해당 set에서 find 함수를 통해서 s2에 있는 원소들에 대해서 해당 원소들이 set에 들어있는 원소들에 존재하는지 찾는 형태로 코드를 작성했다. 이때에 과연 set을 이용한 풀이를 하는것과, 내가 제출한 형태처럼 이중for문을 통해서 풀이하는것이 시간복잡도 측면에서 어떠한 차이가 있는지에 대해서 알기 위해서 gpt을 이용해 답변을 얻어보았다.

---

답변

첫 번째 코드와 두 번째 코드를 비교하여 시간 복잡도 측면에서의 효율성을 살펴보겠습니다.

첫 번째 코드:

int solution(vector<string> s1, vector<string> s2) {
    int answer = 0;
    set<string> s3(s1.begin(), s1.end());
    for(int i = 0; i < s2.size(); i ++)
    {
        if(s3.find(s2[i]) != s3.end())
        {
            answer++;
        }
    }
    return answer;
}

두 번째 코드:

int solution(vector<string> s1, vector<string> s2) {
    int answer = 0;
    for(auto c: s1){
        for(auto s: s2){
            if(c == s) answer++;
        }
    }
    return answer;
}

• 첫 번째 코드에서는 s1 벡터의 원소들을 set 컨테이너 s3에 넣고, s2 벡터의 원소들을 순회하며 s3에 존재하는지 확인하는 방식입니다. set은 이진 검색 트리를 사용하므로 find() 연산이 평균적으로 O(log N) 시간이 걸립니다.

• 두 번째 코드에서는 중첩된 반복문을 사용하여 s1의 각 원소와 s2의 각 원소를 비교하는 방식입니다. 이 방식은 s1과 s2의 크기에 따라 이중 반복문이 동작하므로 시간 복잡도는 O(N*M)입니다.

시간 복잡도 측면에서 봤을 때, 첫 번째 코드가 두 번째 코드보다 효율적입니다. set은 이진 검색 트리를 사용하므로 원소를 검색하는 데 더 효율적이며, 원소의 중복을 허용하지 않아서 중복된 원소를 처리하는 데도 용이합니다. 따라서 첫 번째 코드가 일반적으로 더 빠른 실행 시간을 갖을 것입니다.

---

이 대답은 set 컨테이너 's3'에 데이터를 넣고 해당 데이터들이 rb트리 상에서 자리를 찾아가는데 걸리는 연산시간에 대한 고려가 없다고 생각해서 그것을 고려한 시간복잡도를 요구해보았다

---

추가 답변

첫 번째 코드에서 set 컨테이너 s3에 원소들을 넣을 때의 정렬에 걸리는 연산 시간은 다음과 같이 살펴볼 수 있습니다.

set<string> s3(s1.begin(), s1.end());

이 코드에서 s1 벡터의 원소들을 set 컨테이너 s3에 복사하는 과정에서 set은 자동으로 원소를 정렬합니다. 이 과정에서 set은 자체적으로 이진 검색 트리(레드-블랙 트리)를 사용하여 원소를 정렬합니다.

이진 검색 트리에 원소를 삽입하는 데 걸리는 시간은 평균적으로 O(log N)입니다. s1 벡터의 크기가 N이라면, s3 컨테이너에 원소를 삽입하는 데는 O(N * log N)의 시간이 소요됩니다. 이는 set 컨테이너의 원소 정렬 과정에 해당합니다.

따라서 첫 번째 코드의 시간 복잡도는 다음과 같이 요약할 수 있습니다:

1. s1 벡터를 set 컨테이너 s3로 복사하고 정렬하는 데 O(N * log N) 시간이 걸립니다.
2. s2 벡터를 순회하며 s3에서 원소를 찾는 데는 평균적으로 O(log N) 시간이 걸립니다.
3. 따라서 전체 시간 복잡도는 O(N * log N + M * log N)입니다. 여기서 M은 s2 벡터의 크기를 나타냅니다.

이에 비해 두 번째 코드의 시간 복잡도는 O(N * M)이므로, 일반적으로 입력 데이터 크기에 따라 첫 번째 코드가 더 효율적입니다.

---

이때에 m의 값과 n의 값이 양쪽다 커진 경우 연산에 있어서 얼마나 차이가 나는지 알아보기 위해서 예를 들어서 한번 비교해보았다.

---

예를 통한 비교

N=1000, M=1000인 경우 NlogN + MlogN과 M*N의 크기를 비교해보겠습니다.

1. NlogN + MlogN:

   • N*logN = 1000 * log2(1000) ≈ 9965 (로그는 자연로그인 경우)
   • M*logN = 1000 * log2(1000) ≈ 9965
   • 따라서 NlogN + MlogN ≈ 2 * 9965 ≈ 19930

2. M*N:

   • M*N = 1000 * 1000 = 1,000,000

N=1000, M=1000인 경우, NlogN + MlogN은 약 19,930이고, MN은 1,000,000입니다. 이 예에서는 MN이 훨씬 큰 값을 갖습니다. 그러나 두 값 사이의 상대적인 크기는 입력 값과 사용되는 알고리즘에 따라 달라질 수 있습니다. 알고리즘의 성능과 병렬 처리 능력을 고려하여 적절한 알고리즘을 선택하는 것이 중요합니다.

---

위의 답변을 통해서, 내가 푼 풀이의 경우는 사이즈가 커지면 굉장히 비효율적인 형태의 코드가 되고, set을 이용한 형태, 즉 rb트리를 이용한 풀이의 경우는 사이즈가 커져도 아주 효율적으로 동작할 수 있는 풀이라는 것을 알 수 있었다.
이처럼 잦은 검색이 필요한 경우는 이중for문 같은 형태를 사용하지말고, rb트리 등을 이용하는 형태의 코드를 작성하는것이 굉장히 효율적이고, c++에서 rb트리를 이용한 컨테이너의 경우는 set 이기 때문에, set을 이용해서 이러한 형태의 문제를 푸는것이 효율적인 방식일는걸 알 수 있었다.