[2025.01.22] Unreal_7기 | 챕터 3. C++과 Unreal Engine으로 3D 게임 개발

코드카타

 

문제 설명
배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항
array의 길이는 1 이상 100 이하입니다.
array의 각 원소는 1 이상 100 이하입니다.
commands의 길이는 1 이상 50 이하입니다.
commands의 각 원소는 길이가 3입니다.
입출력 예
array commands return
[1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;

    for (int i = 0; i < numbers.size()-1; i++)
    {
        for (int j = i+1; j < numbers.size(); j++)
        {
            auto it = find(answer.begin(), answer.end(), numbers[i] + numbers[j]);
            if (it == answer.end())
            {
                answer.push_back(numbers[i] + numbers[j]);
            }
        
        }
    }

    sort(answer.begin(), answer.end());

    return answer;
}

 

경우의 수를 구하고 더한 값을 저장하는 데 find로 검색해 이미 있는 값이면 저장 안하는 로직으로 구현해 봤다.

 

구현하고 AI를 통해 구현시켜 내거와 비교해봤다.

#include <string>
#include <vector>
#include <set> // 중복을 허용하지 않고 자동으로 정렬해주는 컨테이너 헤더

using namespace std;

vector<int> solution(vector<int> numbers) {
    // 1. 중복 제거와 오름차순 정렬을 위해 set 컨테이너 선언
    // set은 값을 넣으면 자동으로 정렬되며, 이미 있는 값은 추가되지 않습니다.
    set<int> unique_sums;

    // 2. 이중 반복문을 통해 서로 다른 인덱스의 두 수 더하기
    // 바깥쪽 루프: 첫 번째 수 선택 (마지막 요소 전까지)
    for (int i = 0; i < numbers.size(); ++i) {
        // 안쪽 루프: 두 번째 수 선택 (첫 번째 수 다음 인덱스부터)
        // j를 i + 1부터 시작함으로써 서로 다른 인덱스를 보장하고 중복 계산을 방지함
        for (int j = i + 1; j < numbers.size(); ++j) {
            int sum = numbers[i] + numbers[j];
            unique_sums.insert(sum); // 계산된 합을 set에 삽입 (자동 정렬/중복 제거)
        }
    }

    // 3. set에 저장된 결과를 반환 타입인 vector로 변환
    // set의 시작(begin)부터 끝(end)까지의 요소를 사용하여 vector 생성
    vector<int> answer(unique_sums.begin(), unique_sums.end());

    return answer;
}

 

1. set에 이 값들이 들어가면 중복인 3, 4, 5는 한 번만 저장되고 순서대로 정렬됩니다.
   • set 내부 상태: {2, 3, 4, 5, 6, 7}
2. 마지막으로 이 내용을 vector로 변환하여 반환합니다.

std::set을 사용하지 않고 vector만 사용하여 풀고 싶으시다면, 모든 합을 vector에 넣은 뒤 sort(정렬) 함수와 unique(중복 제거) 함수를 차례로 적용해야 합니다. 하지만 set을 사용하는 것이 이 문제의 의도에 더 적합하고 깔끔한 풀이입니다.

더 궁금한 점이 있으시거나 다른 방식의 풀이가 필요하시면 말씀해 주세요.

 

이 구현을 보면서 Set에 대해 정리 해봤다.

 

Set

std::set은 C++ 표준 템플릿 라이브러리(STL)에서 제공하는 연관 컨테이너(Associative Container) 중 하나입니다. 데이터를 저장할 때 특정 규칙에 따라 자동으로 정렬하고, 중복된 값을 허용하지 않는 것이 가장 큰 특징입니다.

이전 문제 풀이에서 set을 사용한 이유는 "중복을 제거"하고 "오름차순으로 정렬"해야 한다는 두 가지 조건을 한 번에 만족시킬 수 있었기 때문입니다.

---

1. std::set의 핵심 특징

1. 중복 불가 (Unique Keys)
   • 이미 set 안에 존재하는 값을 다시 넣으려고(insert) 하면, 새로운 값은 무시됩니다. 즉, 컨테이너 안에는 항상 유일한 값만 존재합니다.
2. 자동 정렬 (Ordered)
   • 데이터를 넣는 순서와 상관없이, 내부적으로 설정된 정렬 기준(기본값: 오름차순)에 따라 자동으로 정렬되어 저장됩니다.
3. 구현 방식 (Balanced Binary Search Tree)
   • 내부적으로 **레드-블랙 트리(Red-Black Tree)**라는 균형 이진 탐색 트리 구조로 구현되어 있습니다.
   • 이 때문에 데이터의 탐색, 삽입, 삭제에 걸리는 시간 복잡도가 **$O(\log n)$**으로 매우 빠르고 안정적입니다.

2. 주요 멤버 함수 (기능)

자주 사용되는 set의 기능들입니다.

함수 이름	설명
insert(k)	값 k를 삽입합니다. 이미 있다면 무시하고, 없다면 정렬된 위치에 넣습니다.
erase(k)	값 k를 찾아서 삭제합니다.
find(k)	값 k가 있는지 찾습니다. 값을 찾으면 해당 위치의 반복자(iterator)를 반환하고, 없으면 end()를 반환합니다.
size()	현재 저장된 원소의 개수를 반환합니다.
empty()	비어있으면 true, 아니면 false를 반환합니다.
clear()	모든 원소를 삭제하여 비웁니다.
begin()	첫 번째 원소를 가리키는 반복자를 반환합니다.
end()	마지막 원소의 다음을 가리키는 반복자를 반환합니다. (실제 값이 없는 끝 표식)