[SWEA] 1230번 암호문 3 (C++)

SW Expert Academy

링크드 리스트를 직접 구현하여 풀었다.

메모리 풀을 이용하여 메모리를 아껴준다.

#include <iostream>
using namespace std;
struct Node
{
    int data;
    Node *next;
};
Node memPool[10000]; // 사용할 노드 미리 정의 (메모리 풀)
Node *head;         // 링크드 리스트의 대가리
int N, M, num, memPoolCnt, x, y, s;
char order;

Node *getNode(int num)
{
    memPool[memPoolCnt].data = num;
    memPool[memPoolCnt].next = nullptr;
    return &memPool[memPoolCnt++];
}

int main()
{
    for (int t = 1; t <= 10; t++)
    {
        cin >> N;
        memPoolCnt = 0; // 메모리 풀 초기화
        head = nullptr; // 링크드 리스트 초기화
        int tmp =0;
        Node *ptr = nullptr;
        // 원본 암호문
        for (int i = 0; i < N; i++)
        {
            cin >> num;
            Node *newNode = getNode(num);
            if (head == nullptr) {
                head = newNode; // head가 null이면 새로 만듦
                ptr = head;
            }
            else
            {
                ptr->next = newNode; // head의 맨 뒤에 새 노드 추가
                ptr = ptr->next; // 다음 노드 가리킴
                tmp++;
            }
        }
        cin >> M;
        // 명령어 수행
        for (int i = 0; i < M; i++){
            cin >> order;
            switch (order)
            {
                case 'I': // 삽입
                {
                    cin >> x >> y;
                    Node *ptr = head;
                    int cnt = x;
                    while(cnt > 1) {
                        ptr = ptr->next; // x번째 위치 찾음
                        cnt--;
                    }
                    for(int i = 0; i < y; i++){
                        cin >> s;
                        Node *newNode = getNode(s);
                        if(i == 0 && x == 0) { // x가 0이면 맨 앞에 집어 넣음
                            newNode->next = head;
                            head = newNode;
                            ptr = head;
                            continue;
                        }
                        newNode->next = ptr->next; // 새 노드의 next는 현재 노드의 next
                        ptr->next = newNode; // 현재 노드의 next는 새 노드
                        ptr = ptr->next; // 바로 다음 노드 가리킴
                    }
                }
                	break;
                case 'D': // 삭제
                {
                    cin >> x >> y;
                    Node *ptr = head;
                    int cnt = x;
                    while(cnt > 1) {
                        ptr = ptr->next; // x번째 위치 찾음
                        cnt--;
                    }
                    for(int i = 0; i < y; i++){
                        if(ptr->next == nullptr){
                            ptr = nullptr; // 다음 노드가 없으면 현재 노드를 nullptr로 만듦
                            break;
                        } 
                        if(x == 0){
                            head = head->next;
                            ptr = head;
                            continue;
                        } 
                        ptr->next = ptr->next->next; // 현재 노드의 next를 다음 노드의 next로 지정
                    }
                }
                	break;
                case 'A': // 추가
                {
                    cin >> y;
                    Node* ptr = head;
                    while(ptr->next) ptr = ptr->next; // 맨 뒤 노드 찾음
                    for (int i = 0; i < y; i++){
                        cin >> s;
                        Node *newNode = getNode(s);
                        ptr->next = newNode; // 맨 뒤 노드에 새 노드 추가
                        ptr = ptr->next; // 다음 노드를 가리킴
                    }
                }
                	break;
            }
        }
        // 수정 후 암호문 10개 출력
        cout << "#" << t << " ";
        for (int i = 0; i < 10; i++){
            cout << head->data << " ";
            head = head->next;
        }
        cout << "\n";
    }
}