C++ 백준 5397 키로거

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

처음 한 풀이

#include <iostream>
using namespace std;
const int MX = 1000005;
char dat[MX];
int pre[MX];
int nxt[MX];
int unused = 1;

void insert(int addr, char c) { // addr 뒤에 삽입
    dat[unused] = c;
    pre[unused] = addr;
    nxt[unused] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = unused;
    nxt[addr] = unused;
    unused++;
}

void erase(int addr) {
    nxt[pre[addr]] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

void traverse() {
    int cur = nxt[0];
    while(cur != -1) {
        cout << dat[cur];
        cur = nxt[cur];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    unused = 1;
    int t;
    cin >> t;
    while(t--) {
        int cur = 0; // 각 테스트 케이스마다 cur을 0으로 초기화
        fill(pre, pre+MX, -1); 
        fill(nxt, nxt+MX, -1); // 각 테스트 케이스마다 pre와 nxt를 -1로 초기화
        string s;
        cin >> s;
        for(auto c : s) {
            if(c == '<') {
                if(pre[cur] != -1) // 첫번째 원소가 아닌 경우
                    cur = pre[cur];
            }
            else if(c == '>') { // 마지막 원소가 아닌 경우
                if(nxt[cur] != -1)
                    cur = nxt[cur];
            }
            else if(c == '-') {
                if(cur != 0) { // 빈 리스트가 아닌 경우
                    erase(cur);
                    cur = pre[cur];
                }
            }
            else {
                insert(cur, c);
                cur = nxt[cur];
            }
        }
        traverse();
    }
}

1. 문자열 길이가 1,000,000이하 이므로 MX를 1,000,005로 여유있게 설정하였다.
2. 처음 풀이할때 OutOfBounds 에러가 떠서 확인해보니 각 테스트 케이스마다 unused를 1로 초기화 해주지 않아서, 테스트 케이스를 진행할 수록 누적 데이터가 MX를 넘어서서 발생한 문제임을 확인 하여 수정하였다.
3. cur을 이동할 때 배열처럼 cur--, cur++로 이동하는 것이 아니라 pre[cur], nxt[cur]을 이용하여 이동하여야 한다.(연결리스트는 연속된 메모리 공간을 보장할 수 없기 때문)

배운 풀이

#include <iostream>
#include <list>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--) {
        list<char> l = {};
        auto p = l.begin();
        string s;
        cin >> s;
        for(auto c:s) {
            if(c == '<') {
                if(p != l.begin()) // 처음 원소가 아닌 경우
                    p--;
            }
            else if(c == '>') {
                if(p != l.end()) // 마지막 원소가 아닌 경우
                    p++;
            }
            else if(c == '-') {
                p--; // 다음 원소를 가리키고 있으므로 p--후 erase
                p = l.erase(p); // erase는 제거한 다음 위치의 원소를 반환
            }
            else {
                l.insert(p, c); // p앞에 추가
            }
        }
        for(auto item: l) cout << item;
        cout << '\n';
    }

}

STL list를 이용하여 쉽게 구현할 수 있다.

STL list의 경우 insert(p, data)함수가 p앞에 추가되므로 p를 증가 시키지 않아야 함을 깨달았다. p값은 l.begin()으로 초기 설정을 해놓고, insert를 하면 초기 설정한 p를 기준으로 앞에 계속 원소를 추가해 나가는 것이었다.