교재 연습문제

• 『코딩 테스트를 위한 자료구조와 알고리즘 with C++』 33~37페이지

#include <iostream>
#include <sstream>
#include <algorithm>

// 클래스의 멤버 변수/함수들이 자료형만 다르고 같을 때 사용
// type을 T로 선언
template <typename T>
class dynamic_array
{
    T* data;
    size_t n;

public:
    // 배열 크기를 인자로 받는 생성자(constructor)
    dynamic_array(int n)
    {
        this->n = n;
        data = new T[n];
    }

    // 복사 생성자(constructor)
    dynamic_array(const dynamic_array<T>& other)
    {
        n = other.n;
        data = new T[n];

        for (int i = 0; i < n; i++)
            data[i] = other[i];
    }

    // 멤버 데이터에 직접 접근하기 위한 []연산자
    T& operator[](int index)
    {
        return data[index];
    }

    const T& operator[](int index) const
    {
        return data[index];
    }

    // 멤버 데이터에 직접 접근하기 위한 at 함수
    T& at(int index)
    {
        if (index < n)
            return data[index];
        throw "Index out of range";
    }

    // 배열의 크기를 반환하는 size 멤버 함수
    size_t size() const
    {
        return n;
    }

    // 소멸자(deconstructor)
    ~dynamic_array()
    {
        delete[] data;  // 메모리 릭 방지
    }

    // 배열 원소를 순회할 때 사용할 반복자 함수
    T* begin() { return data; }
    const T* begin() const { return data; }
    T* end() { return data + n; }
    const T* end() const { return data + n; }

    // 두 배열을 하나로 합치는 +연산자 함수
    friend dynamic_array<T> operator+(const dynamic_array<T>& arr1, dynamic_array<T>& arr2)
    {
        dynamic_array<T> result(arr1.size() + arr2.size());
        std::copy(arr1.begin(), arr1.end(), result.begin());
        std::copy(arr2.begin(), arr2.end(), result.begin() + arr1.size());

        return result;
    }

    // 배열에 저장된 모든 데이터를 문자열로 반환하는 to_string 함수
    std::string to_string(const std::string& sep=", ")
    {
        if(n == 0)
            return "";
        
        std::ostringstream os;
        os << data[0];

        for (int i = 1; i < n; i++)
            os << sep << data[i];

        return os.str();
    }
};

// 학생 정보를 저장할 구조체 student 정의
// 학생의 이름 name과 학생의 학급 정보 standard 멤버를 가짐
// << 연산자를 이용한 표준 출력 지원
struct student
{
    std::string name;
    int standard;
};

std::ostream& operator<<(std::ostream& os, const student& s)
{
    return (os << "[" << s.name << ", " << s.standard << "]");
}

// main 함수에서 dynamic_array를 사용하는 코드 작성
int main()
{
    int nStudents;
    std::cout << "1반 학생 수를 입력하세요: ";
    std::cin >> nStudents;

    dynamic_array<student> class1(nStudents);
    for (int i = 0; i < nStudents; i++)
    {
        std::string name;
        int standard;
        std::cout << i + 1 << "번째 학생 이름과 나이를 입력하세요: ";
        std::cin >> name >> standard;
        class1[i] = student{name, standard};
    }

    // 배열 크기보다 큰 인덱스의 학생에 접근
    try
    {
        class1.at(nStudents) = student{"John", 8};  // 예외 발생
    }
    catch(...)
    {
        std::cout << "예외 발생!" << std::endl;
    }

    // 깊은 복사
    auto class2 = class1;
    std::cout << "1반을 복사하여 2반 생성: " << class2.to_string() << std::endl;

    // 두 학급을 합쳐서 새로운 큰 학급을 생성
    auto class3 = class1 + class2;
    std::cout << "1반과 2반을 합쳐 3반 생성: " << class3.to_string() << std::endl;

    return 0;
    
}

백준 29729번

가변 배열의 초기 크기와, 일련의 원소 저장 또는 삭제 명령이 주어졌을 때, 명령들을 모두 수행한 후 가변 배열의 최대 크기를 출력해 보자.

#include <iostream>
#include <vector>

using namespace std;

int process_commands(int initial_size, const vector<int>& commands) {
    int current_size = initial_size;
    int used_size = 0;
    vector<int> dynamic_array;

    for (int command : commands) {
        if (command == 1) {
            // 저장 명령인 경우
            used_size++;

            // 현재 사용 중인 크기가 현재 최대 크기보다 크다면 배열 크기를 늘림
            if (used_size > current_size) {
                current_size *= 2;
                // 새로운 크기의 배열을 생성하고 기존 배열의 내용을 복사
                vector<int> new_array(current_size);
                move(dynamic_array.begin(), dynamic_array.end(), new_array.begin());
                dynamic_array = move(new_array);
            }
        } else {
            // 삭제 명령인 경우
            used_size--;
        }
    }

    return current_size;
}

int main() {
    int initial_size, num_store_commands, num_delete_commands;
    cin >> initial_size >> num_store_commands >> num_delete_commands;

    vector<int> commands;
    for (int i = 0; i < num_store_commands + num_delete_commands; ++i) {
        int command;
        cin >> command;
        commands.push_back(command);
    }

    // 결과 출력
    int result = process_commands(initial_size, commands);
    cout << result << endl;

    return 0;
}

문제에 "기존 가변 배열에 있는 원소를 모두 복사한 후, 기존 가변 배열을 지우고" 라는 부분이 있어 기존 값을 이동시키는 move를 사용