자료구조 [예상]

1번

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 끝자리가 작은 순으로, 끝자리가 같다면 숫자 자체가 작은 순으로 정렬하는 함수
bool custom_sort(int a, int b) {
    if (a % 10 == b % 10) // 끝자리가 같다면 숫자 자체가 작은 순
        return a < b;
    return (a % 10) < (b % 10); // 끝자리 기준으로 정렬
}

int main() {
    int N; // 정수의 개수
    cout << "N을 입력하세요: ";
    cin >> N;
    
    vector<int> numbers(N); // N개의 정수를 저장할 벡터
    
    // N개의 숫자 입력
    for (int i = 0; i < N; ++i) {
        cin >> numbers[i];
    }
    
    // 정렬
    sort(numbers.begin(), numbers.end(), custom_sort);
    
    // 결과 출력
    for (int i = 0; i < N; ++i) {
        cout << numbers[i] << endl;
    }

    return 0;
}

 

 

#include <iostream>
#include <vector>

using namespace std;

// 끝자리가 작은 순으로, 끝자리가 같다면 숫자 자체가 작은 순으로 정렬하는 함수
void bubble_sort(vector<int>& numbers) {
    int n = numbers.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            int current_end_digit = numbers[j] % 10;
            int next_end_digit = numbers[j + 1] % 10;

            // 끝자리가 같으면 숫자 자체를 비교, 끝자리가 다르면 끝자리 비교
            if (current_end_digit > next_end_digit || 
               (current_end_digit == next_end_digit && numbers[j] > numbers[j + 1])) {
                // Swap (numbers[j]와 numbers[j+1]를 교환)
                int temp = numbers[j];
                numbers[j] = numbers[j + 1];
                numbers[j + 1] = temp;
            }
        }
    }
}

int main() {
    int N; // 정수의 개수
    cout << "N을 입력하세요: ";
    cin >> N;

    vector<int> numbers(N); // N개의 정수를 저장할 벡터

    // N개의 숫자 입력
    for (int i = 0; i < N; ++i) {
        cin >> numbers[i];
    }

    // 정렬
    bubble_sort(numbers);

    // 결과 출력
    for (int i = 0; i < N; ++i) {
        cout << numbers[i] << endl;
    }

    return 0;
}

코드 설명:

1. 버블 정렬 알고리즘을 사용하여 벡터 내의 숫자를 순차적으로 비교하고, 필요할 경우 인접한 두 값을 교환(swap)합니다.
2. 끝자리 숫자(% 10)로 우선 비교하고, 끝자리가 같으면 숫자 자체를 비교하여 정렬합니다.
3. bubble_sort 함수는 벡터를 받아 정렬 작업을 수행합니다.
4. main 함수에서는 사용자로부터 숫자 개수와 숫자들을 입력받아 버블 정렬을 호출한 뒤 결과를 출력합니다.

2번

주어진 단어 중 특정 단어보다 사전적으로 앞서는 단어 중에서 가장 길이가 긴 단어를 찾는 문제입니다. 만약 그런 단어가 존재하지 않으면 "None"을 출력합니다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 조건에 맞는 가장 긴 단어를 찾는 함수
string find_longest_word(const vector<string>& words, const string& search_word) {
    string longest_word = "None";  // 일치하는 단어가 없으면 None 반환
    for (const auto& word : words) {
        // 사전적으로 search_word보다 앞서고, 길이가 더 긴 단어를 찾는다
        if (word < search_word && word.length() > longest_word.length()) {
            longest_word = word;
        }
    }
    return longest_word;
}

int main() {
    int N;  // 단어의 개수
    cin >> N;
    
    vector<string> words(N);
    
    // N개의 단어 입력
    for (int i = 0; i < N; ++i) {
        cin >> words[i];
    }
    
    string search_word;
    cin >> search_word;  // 검색할 단어 입력
    
    // 가장 긴 단어를 찾고 결과 출력
    string result = find_longest_word(words, search_word);
    cout << result << endl;
    
    return 0;
}

코드 설명:

1. find_longest_word 함수는 주어진 단어 리스트에서 검색 단어보다 사전적으로 앞서는 단어 중에서 가장 긴 단어를 찾는 역할을 합니다. 만약 조건에 맞는 단어가 없다면 "None"을 반환합니다.
2. main 함수에서는 사용자로부터 단어의 개수(N)와 N개의 단어, 그리고 검색할 단어를 입력받습니다.
3. 입력된 단어들을 기준으로 가장 긴 단어를 찾아 출력합니다.

3번

#include <iostream>
#include <cstring>

using namespace std;

// 노드 구조체 정의
struct Node {
    char word[100]; // 단어를 저장할 배열
    Node* next; // 다음 노드를 가리키는 포인터
};

// 연결 리스트의 head 노드
Node* head = nullptr;

// 연결 리스트에 단어를 삽입하는 함수 (사전순으로 삽입)
void insert_word(const char* new_word) {
    Node* new_node = new Node();
    strcpy(new_node->word, new_word);
    new_node->next = nullptr;

    if (head == nullptr || strcmp(new_word, head->word) < 0) {
        new_node->next = head;
        head = new_node;
    } else {
        Node* current = head;
        while (current->next != nullptr && strcmp(current->next->word, new_word) < 0) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

// 연결 리스트에서 W1과 W2 사이의 단어들을 삭제하는 함수
void delete_words_between(const char* W1, const char* W2) {
    Node* current = head;
    Node* prev = nullptr;

    while (current != nullptr) {
        // 현재 단어가 W1보다 크고 W2보다 작은 경우 삭제
        if (strcmp(current->word, W1) > 0 && strcmp(current->word, W2) < 0) {
            Node* temp = current;
            if (prev == nullptr) {
                head = current->next;
            } else {
                prev->next = current->next;
            }
            current = current->next;
            delete temp; // 메모리 해제
        } else {
            prev = current;
            current = current->next;
        }
    }
}

// 연결 리스트의 모든 단어를 출력하는 함수
void print_list() {
    Node* current = head;
    while (current != nullptr) {
        cout << current->word << endl;
        current = current->next;
    }
}

// 연결 리스트의 메모리를 해제하는 함수
void clear_list() {
    Node* current = head;
    while (current != nullptr) {
        Node* temp = current;
        current = current->next;
        delete temp;
    }
}

int main() {
    int N;
    cout << "파일에 저장된 단어의 개수를 입력하세요: ";
    cin >> N;

    // 단어 입력
    for (int i = 0; i < N; ++i) {
        char word[100];
        cin >> word;
        insert_word(word);
    }

    // 현재 리스트 출력
    cout << "\n현재 리스트:\n";
    print_list();

    // W1, W2 입력
    char W1[100], W2[100];
    cout << "\nW1과 W2를 입력하세요: ";
    cin >> W1 >> W2;

    // W1과 W2 사이의 단어 삭제
    delete_words_between(W1, W2);

    // 결과 출력
    cout << "\n삭제 후 리스트:\n";
    print_list();

    // 메모리 정리
    clear_list();

    return 0;
}

코드 설명:

1. 구조체 Node: 각 단어를 저장하고 연결 리스트의 다음 노드를 가리키는 포인터(next)를 포함하는 구조체입니다.
2. insert_word 함수: 단어를 사전순으로 연결 리스트에 삽입합니다. 리스트가 비어 있거나 새 단어가 첫 번째에 위치해야 할 경우, 새 노드를 헤드로 설정합니다.
3. delete_words_between 함수: 주어진 W1과 W2 사이에 위치한 모든 단어를 리스트에서 제거합니다. 메모리 해제도 함께 처리됩니다.
4. print_list 함수: 연결 리스트의 모든 단어를 출력합니다.
5. clear_list 함수: 프로그램 종료 시 연결 리스트에 남은 모든 노드를 삭제하고 메모리를 해제합니다.
6. main 함수: 사용자로부터 입력을 받고, 연결 리스트를 처리하며 최종적으로 결과를 출력합니다.