BOJ 1406 - 에디터 문제 해결 과정 (std::list 활용)

김지섭·2024년 12월 25일

목록 보기

7/26

BOJ 1406 - 에디터 문제 해결 과정 (std::list 활용)

문제 소개

오늘은 BOJ 1406번 '에디터' 문제를 풀며 겪은 시행착오와 해결 과정을 정리해보려고 합니다.
이 문제는 문자열 편집기를 구현하는 것으로, 커서를 이동하고 문자를 삽입/삭제하는 동작을 정확히 수행해야 합니다.
주어진 명령을 효율적으로 처리하기 위해 STL 컨테이너를 어떻게 활용할지 고민할 수 있는 문제입니다.

문제 요구 사항

문자열의 초기 상태와 커서의 시작 위치가 주어집니다. 이후 명령어를 처리하면서 편집기를 구현해야 합니다. 명령어는 다음과 같습니다:

L: 커서를 왼쪽으로 한 칸 옮깁니다. (단, 커서가 맨 앞이면 무시)
D: 커서를 오른쪽으로 한 칸 옮깁니다. (단, 커서가 맨 뒤이면 무시)
B: 커서 왼쪽에 있는 문자를 삭제합니다. (단, 커서가 맨 앞이면 무시)
P x: 커서 왼쪽에 문자 x를 추가합니다.

제약 사항

명령어의 개수는 최대 50만 개입니다.
커서와 문자의 삽입/삭제를 효율적으로 처리해야 합니다.
O(n^2) 이상의 알고리즘은 시간 초과 가능성이 높습니다.

초기 접근 방법

1. `std::vector`를 사용한 구현

처음에는 std::vector를 사용해 구현을 시도했습니다. 하지만 vector는 삽입/삭제 시 커서 이후의 모든 요소를 이동시켜야 하므로, 시간 복잡도가 O(n)으로 증가합니다.
명령어가 최대 50만 개까지 주어지기 때문에, 이 접근법으로는 시간 초과가 발생했습니다.

// vector 기반의 비효율적 접근
vector<char> text(str.begin(), str.end());
int cursor = text.size();

// 삽입과 삭제가 O(n)이라 비효율적
if (cursor > 0) text.erase(text.begin() + (--cursor));

2. `std::list`를 사용한 개선

std::list는 양방향 연결 리스트로, 삽입과 삭제가 O(1)로 가능합니다. 따라서 명령어 처리에서 효율적입니다.
하지만 이 과정에서도 iterator 사용에 미숙해 런타임 에러가 발생했습니다.

문제 발생과 해결

문제: `erase` 호출 후 런타임 에러

초기 코드에서 커서 위치를 업데이트하는 방식에 문제가 있었습니다.

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

std::list::erase는 삭제된 다음 위치의 iterator를 반환합니다. 하지만 위 코드는 cursor를 갱신하지 않아 무효화된 iterator를 계속 사용하게 되었고, 이는 런타임 에러를 유발했습니다.

해결 방법

문제는 간단히 erase 함수의 반환 값을 cursor에 저장해 해결할 수 있습니다. 이를 통해 항상 유효한 iterator를 유지할 수 있습니다.

수정된 코드:

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

이 수정으로 런타임 에러가 해결되었고, 프로그램이 정상적으로 동작하게 되었습니다.

최종 코드

#include <bits/stdc++.h>
using namespace std;

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

    list<char> L;
    string str;
    cin >> str;

    // 초기 문자열을 리스트에 저장
    for (char ch : str) {
        L.push_back(ch);
    }

    list<char>::iterator cursor = L.end();
    int repeat;
    cin >> repeat;

    // 명령어 처리
    for (int i = 0; i < repeat; i++) {
        char choice;
        cin >> choice;
        switch (choice) {
        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 ch;
            cin >> ch;
            L.insert(cursor, ch);
            break;
        }
        default:
            break;
        }
    }

    // 결과 출력
    for (char ch : L) {
        cout << ch;
    }

    return 0;
}

배운 점

std::list의 특징
- list는 양방향 반복자와 빠른 삽입/삭제를 제공하며, 커서 기반 문제에 적합합니다.
- 하지만 반복자 무효화 문제를 주의해야 합니다.
반복자 관리의 중요성
- erase나 insert처럼 반복자를 반환하는 함수를 사용할 때는, 항상 반복자를 업데이트해야 유효성을 유지할 수 있습니다.
문제 해결 과정의 기록
- 시행착오를 기록하며, 비효율적인 접근법을 어떻게 개선했는지 정리하면 다음에 비슷한 문제를 풀 때 큰 도움이 됩니다.

느낀 점

이번 문제를 통해 반복자와 연결 리스트의 특성을 더 깊이 이해할 수 있었습니다. 특히, 효율적인 자료구조 선택의 중요성을 다시 한번 느꼈습니다. 앞으로 더 복잡한 문제를 풀더라도 차분히 원인을 분석하고 해결하는 습관을 길러야겠다고 다짐하게 되었습니다.

비슷한 유형의 문제로는 BOJ 5397번 '키로거'가 있으니 참고하시면 좋을 것 같습니다. 😊

이 글을 통해 다른 분들도 std::list와 반복자의 사용법을 이해하고, 문제를 효율적으로 해결하는 데 도움을 받으셨으면 좋겠습니다! 🙌

김지섭

백엔드 행 유도 미사일

이전 포스트

[백준] 11050번

다음 포스트

BOJ 1406 - 에디터 문제 해결 과정 (std::list 활용)

백준