Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Hepheir

1230. 암호문3

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.

(문제 출처: SW Expert Academy)

  • 원소들을 추가/제거해야 하는 빈도가 잦으므로 Array보다는 Linked list를 사용하는 것이 적합.
  • std::list의 Iterator를 다룰 때, Iterator를 $n$칸 전진시키기 위해 $O(n)$의 시간이 걸림에 유의하여, 최대한 적은 횟수로 Iterator를 전진 시키도록 구현.
    • I삽입 명령 시 $x$번 위치 부터 총 $y$개의 원소를 list::insert()로 하나 씩 넣게 되면, 총 $T(xy+\frac{1}{2}y^2)$의 시간이 소요된다.
    • 별도의 리스트1를 생성하여 총 $y$개의 원소를 list::push_back()으로 $T(y)$에 삽입하고, list::splice()를 이용하여 기존의 리스트와 $T(x+y)$에 병합할 경우, 동일한 작업을 $T(x+2y)$ 시간에 수행 할 수 있다.
  • Singly-linked liststd::forward_list 대신 Doubly-linked liststd::list를 사용하여, 사용빈도가 높은 push_back() 연산을 $O(1)$ 시간에 수행 할 수 있도록 함.
#include <list>
#include <iostream>

#define MAX_N 4000
#define MAX_M 500

using namespace std;

void solveTestCase()
{
    int codeCount, operationCount;
    char operationType;
    int i, x, y, s;
    string code;
    list<string> codes;
    list<string> codeSnippets;
    list<string>::iterator start, end;
    cin >> codeCount;
    for (i = 0; i < codeCount; i++) {
        cin >> code;
        codes.push_back(code);
    }
    cin >> operationCount;
    for (i = 0; i < operationCount; i++) {
        cin >> operationType;
        switch (operationType) {
            case 'I':
                cin >> x >> y;
                codeSnippets.clear();
                for (s = 0; s < y; s++) {
                    cin >> code;
                    codeSnippets.push_back(code);
                }
                codes.splice(next(codes.begin(), x), codeSnippets);
                break;

            case 'D':
                cin >> x >> y;
                start = end = next(codes.begin(), x);
                advance(end, y);
                codes.erase(start, end);
                break;

            case 'A':
                cin >> y;
                for (s = 0; s < y; s++) {
                    cin >> code;
                    codes.push_back(code);
                }
                break;

            default:
                break;
        }
    }
    start = end = codes.begin();
    advance(end, 10);
    while (start != end) {
        cout << *start << ' ';
        start++;
    }
    return;
}

void solve()
{
    for (int testCaseNo = 1; testCaseNo <= 10; testCaseNo++) {
        cout << '#' << testCaseNo << ' ';
        solveTestCase();
        cout << '\n';
    }
    return;
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("sample_input.txt", "r", stdin);
    freopen("sample_output.txt", "w", stdout);
    solve();
    return 0;
}

  1. 코드에서는 list<string> codeSnippets이다. ↩

Back to top