c++ 4. 연결리스트 연습문제

c++ <string> 라이브러리

1. string의 크기는 이론적으론 무한, 메모리가 되는 데까지 가능
2. 문자열의 끝을 표시하는 '\0' 대신 string 클래스 내에서 길이를 따로 갖고 있음
3. 맨 뒤에 더미노드 존재 L.end()

1. L.insert(t, 2) -> t 커서 앞에 추가
2. L.erase(t) -> t커서가 가리키는 값 삭제, 다음 위치를 가리킴

​

연습 문제 풀이

​

1. 백준 s2 1406 에디터

https://www.acmicpc.net/problem/1406

​

풀이

커서를 _라고 표시하면,

(_a) (_b) (_c) (_ )

커서가 한 문자를 가리킴 == 그 문자의 앞에 커서가 있음 으로 두고 풀었다

​

백스페이스

/*boj s2 1406 에디터*/
#include <iostream>
#include <string>
#include <list>

using namespace std;

int M;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string str;
    cin >> str;
    cin >> M;
    char command;
    list<char> L;
    for (auto s : str)
    {
        L.push_back(s);
    }
    auto cursor = L.end();
    while (M--)
    {
        cin >> command;

        switch (command)
        {
        case 'L':
            if (cursor != L.begin())
                cursor--;
            break;

        case 'D':
            if (cursor != L.end())
                cursor++;
            break;

        case 'B':
            if (cursor != L.begin())
            {
                cursor = L.erase(--cursor);
            }
            break;

        case 'P':
            char text;
            cin >> text;

            L.insert(cursor, text);
            break;
        }
    }
    for (auto l : L)
    {
        cout << l;
    }
}

 

 

 

2. s2 5397 키로거

https://www.acmicpc.net/problem/5397

​

풀이

1번문제와 거의 동일

 

/*boj s2 5397 키로거*/
#include <iostream>
#include <list>
#include <string>
using namespace std;

int T;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        list<char> pw;
        auto cursor = pw.begin();

        string input;
        cin >> input;

        for (auto c : input)
        {
            switch (c)
            {
            case '<':
                if (cursor != pw.begin())
                    cursor--;
                break;

            case '>':
                if (cursor != pw.end())
                    cursor++;
                break;

            case '-':
                if (cursor != pw.begin())
                {
                    cursor = pw.erase(--cursor);
                }
                break;

            default:
                pw.insert(cursor, c);
                break;
            }
        }
        // 출력
        for (auto l : pw)
        {
            cout << l;
        }
        cout << endl;
    }
}

 

3. s4 1158 요세푸스 문제

https://www.acmicpc.net/problem/1158

​

풀이

​

circular linked list

cursor++을 하되, 만약 L.end()에 다다르면 L.begin()으로 옮겨주었다

주의할 점은 cursor++이나 L.erase(cursor)를 하면서 cursor가 이동하므로, 그 경우를 생각해서 cursor++의 앞 뒤로 예외처리를 해줌

/*boj s4 1158 요세푸스 문제*/
#include <iostream>
#include <list>
#include <vector>
using namespace std;

int N, K;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;

    // 1. 입력
    list<int> L;
    for (int i = 1; i <= N; i++)
        L.push_back(i);
    auto cursor = L.begin();
    vector<int> result;

    // 2. 요세푸스
    while (!L.empty())
    {
        // 2-1. K번 커서 옮기기
        for (int k = 0; k < K - 1; k++)
        {
            if (cursor == L.end())
                cursor = L.begin();
            cursor++;
            if (cursor == L.end())
                cursor = L.begin();
        }

        // 2-2. 커서가 가리키는 숫자 삭제
        result.push_back(*cursor);
        cursor = L.erase(cursor);
    }

    // 3. 출력
    cout << "<";
    for (int v : result)
    {
        cout << v;
        if (v != result[N - 1])
            cout << ", ";
    }
    cout << ">\n";
}
​