[SWEA/D3] 1230. [S/W 문제해결 기본] 8일차 - 암호문3

🔗 문제

SW Expert Academy

SW Expert Academy

 

 

🖍 풀이

양방향 리스트를 지원하는 컨테이너 list 를 활용해서 풀어도 된다. 

1. 기존 암호문: list의 뒤에 데이터를 연달아 삽입한다.
2. 새 암호문: list는 임의 위치 엑세스가 불가하다는 특징이 있다. 그래서 string이나 vector처럼 container[i+x]가 불가능하다. 대신 반복자 iter를 사용해주었다. list의 begin()부터 x번 반복자를 이동시켜야 삽입할 위치를 iter에 저장한다. 그리고 나서 insert(삽입 위치, 데이터)하여 새 암호문을 넣어준다.
3. 이 때, 명령문마다 삽입할 위치 (x)가 다르므로 iter = list.begin() 초기화하는 것을 잊지 말 것!
4. 암호문 출력: 문제를 잘 보자 list의 처음부터 10개만 출력해야 한다.

 

 

💾  소스

list 라이브러리

#include <iostream>
#include <list>

int main()
{
    int T = 10;
    for(int tc=1 ; tc<=T; ++tc)
    {
        std::list<int> list;
        int N, cnt, data;
        int x, y, s;
        char op;
        
        std::cin >> N;
        for(int i=0; i<N; ++i)
        {
            std::cin >> data;
            list.emplace(list.end(), data);
        }
        
        auto Iter = list.begin();
        std::cin >> cnt;
        for(int i=0; i<cnt; ++i)
        {
            std::cin >> op;
            
            if(op == 'I')
            {
                std::cin >> x >> y;
                for(int j=0; j<x; ++j)
                    ++Iter;
                for(int j=0; j<y; ++j)
                {
                    std::cin >> s;
                    list.insert(Iter, s);
                }
                Iter = list.begin();
            }
            else if(op == 'D')
            {
                std::cin >> x >> y;
                for(int j=0; j<x; ++j)
                    ++Iter;
                auto Iter2 = Iter;
                for(int j=0; j<y; ++j)
                    ++Iter2;
                list.erase(Iter, Iter2);
            }
            else if(op=='A')
            {
                std::cin >> y;
                for(int j=0; j<y; ++j)
                {
                    std::cin >> s;
                    list.push_back(s);
                }
            }
            Iter = list.begin();
        }
        
        cnt = 0;
        std::cout << '#' << tc << ' ';
        while(cnt++ != 10)
        {
            std::cout << *Iter++ << ' ';
        }
        std::cout << '\\n';
        
        
    }
    return 0;
}

 

LinkedList

#include <iostream>

const int poolSize = 10000;
int poolCnt = 0;
int N, M;
int data, x, y;

struct Node
{
    Node()
    : next(nullptr), data(0)
    {};
    
    Node* next;
    int data;
};

Node* head = nullptr;
Node* iter = nullptr;
Node pool[poolSize];
Node* getNode(int _data)
{
    pool[poolCnt].data = _data;
    pool[poolCnt].next = nullptr; // tc 돌릴 때마다 초기화 필요해서 필수.
    return &pool[poolCnt++];
}

//head에서부터 n번째 노드를 찾는 함수
Node* findNode(Node* ptr, int n)
{
    // 1번째 노드를 찾는다 -> head 가르키면 됨 -> 굳이 1번 이동하지 않아도 됨
    for(int i=1; i<n; ++i)
        ptr = ptr->next;
    
    return ptr;
}

void Insert()
{
    std::cin >> x >> y;
    
    auto iter = findNode(head, x);

    for(int i=0; i<y; ++i)
    {
        std::cin >> data;
        
        auto newNode = getNode(data);
        
        // 맨 앞에 노드를 추가하려고 할 때는 head를 변경해야함
        if(i==0 && x==0)
        {
            newNode->next = head;
            head = newNode;
        }
        else
        {
            newNode->next = iter->next;
            iter->next = newNode;
        }
        iter = newNode;
    }
}

void Delete()
{
    std::cin >> x >> y;
    
    auto iter = findNode(head, x);
    
    for(int i=0; i<y; ++i)
        iter->next = iter->next->next;
}

void Add()
{
    std::cin >> y;
    Node* iter = head;
    
    while(iter->next) iter = iter->next;
  
    for(int i=0; i<y; ++i)
    {
        std::cin >> data;

        Node* newNode = getNode(data);
        iter->next = newNode;
        iter = newNode;
    }
}

int main()
{
    int T = 10;
    for(int tc = 1; tc<=T; ++tc)
    {
        char op;
        head = nullptr;
        iter = nullptr;
        poolCnt = 0;
        
        std::cin >> N;
        for(int i=0; i<N; ++i)
        {
            std::cin >> data;
            
            auto newNode = getNode(data);
            
            if(head == nullptr) head = newNode;
            else iter->next = newNode;
            
            iter = newNode;
        }
        
        std::cin >> M;
        while(M--)
        {
            std::cin >> op;
            if(op == 'I') Insert();
            else if(op == 'D') Delete();
            else if (op == 'A') Add();
        }
        
        std::cout << '#' << tc << ' ';
        for(int i=0; i<10; ++i)
        {
            std::cout << head->data << ' ';
            head = head->next;
        }
        std::cout << '\\n';
    }
    return 0;
    
}