[백준(BOJ)] 1406번 에디터 C++

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

1406번: 에디터

 

어떤 문제인가?

문자열을 입력받고 가상의 커서가 존재해서 문자와 문자 사이를 왔다 갔다 하며 삭제하거나 추가하는 기능을 구현하면 된다.

사실 우리가 키보드로 타이핑할 때와 똑같은 경우이다.

그리고 모든 연산이 끝난 후의 문자열을 출력하면 된다.

 

접근 방법

vector<char> text;
    string input, order;
    int M;

    cin >> input >> M;
    int cursor = input.size();

    for (int i = 0; i < input.length(); i++) {
        text.push_back(input[i]);
    }

    for (int i = 0; i < M; i++) {
        cin >> order;
        if (order == "L") {
            if (cursor != 0) {
                cursor--;
            }
        } else if (order == "D") {
            if (cursor != text.size()) {
                cursor++;
            }
        } else if (order == "B") {
            if (cursor != 0) {
                text.erase(text.begin() + cursor - 1);
                cursor--;
            }
        } else if (order == "P") {
            char add;
            cin >> add;
            text.insert(text.begin() + cursor, add);
            cursor++;
        }
    }

    for (char c: text) {
        cout << c;
    }
    cout << endl;

시간 초과가 발생한 첫 번째 코드이다. 

벡터를 선언하고 커서를 직접 움직이면서 기능을 구현하도록 했다.

벡터를 사용하다보니 erase, insert함수를 사용해서 시간 초과가 발생한 것 같았다.

 

어떻게든 삭제와 삽입은 해야하기 때문에 벡터가 올바른 자료구조가 아니라고 생각했다.

또, 커서를 하나하나 움직이는 것이 불필요하다고 느껴졌다.

 

그래서 생각해낸 방법이 커서는 가만히 있고 커서를 기준으로 왼쪽, 오른쪽에 문자를 담거나 삭제하는 자료구조를 두는 것이다.

 

쉽게 말하면 abcd가 입력되면

왼쪽             오른쪽

abcd (커서) 

인 것이다.

 

P x 입력

왼쪽               오른쪽

abcdx (커서) 

 

L 입력

왼쪽               오른쪽

abcd (커서)   x

 

P y 입력 

왼쪽               오른쪽

abcdy (커서)   x

 

이제 왼쪽부터 출력해주면 

abcdyx가 출력되는 것이다.

 

자료구조는 deque를 사용하기로 했다.

왜냐하면 왼쪽 컨테이너는 뒤에서 삭제와 삽입이 일어나고

오른쪽 컨테이너는 앞에서 삭제와 삽입이 일어나기 때문이다.

push_front, push_back, pop_front, pop_back을 사용하기 완벽하다고 생각했다.

 

 

deque<char> cursorLeft;
deque<char> cursorRight;

 char를 저장하는 deque를 두 개 생성했다.

 

string input, order;
int M;
cin >> input >> M;

for (int i = 0; i < input.length(); i++) {
    cursorLeft.push_back(input[i]);
}

주어진 변수들을 선언하고 입력받는다.

이때 왜 left에 push_back 해주냐면 처음 입력이 끝났을 때는 커서가 맨 뒤쪽에 있기 때문이다.

즉 커서를 기준으로 왼쪽에 문자들이 입력됐다는 소리다.

 

for (int i = 0; i < M; i++) {
    cin >> order;
    if (order == "L") {
        if (!cursorLeft.empty()) {
            cursorRight.push_front(cursorLeft.back());
            cursorLeft.pop_back();
        }
    } 

for문을 입력받은 M번만큼 반복하며 명령어를 입력받는다.

L이 입력됐다면 커서를 왼쪽으로 한 칸 옮겨야 한다.

이를 내 방식대로 한다면 왼쪽 deque의 back을 오른쪽 deque의 front에 넣어주고

왼쪽 deque를 pop_back 해주면 된다.

 

또, 커서가 문장의 맨 앞이면 무시된다는 문제의 조건에 따라 왼쪽 deque가 비어있지 않을 때(커서가 맨 앞이 아님)만 이를 수행하면 된다.

 

 

else if (order == "D") {
    if (!cursorRight.empty()) {
        cursorLeft.push_back(cursorRight.front());
        cursorRight.pop_front();
    }
} 

D가 입력됐다면 커서를 오른쪽으로 한 칸 옮겨야 한다.

L이 입력됐을 때와 정확히 반대로 하면 된다.

오른쪽 deque의 front를 왼쪽 deque의 back에 넣어주고

오른쪽 deque를 pop_front 해주면 된다.

 

또, 커서가 문장의 맨 뒤면 무시된다는 문제의 조건에 따라 오른쪽 deque가 비어있지 않을 때(커서가 맨 뒤가 아님)만 이를 수행하면 된다.

 

 

 

else if (order == "B") {
    if (!cursorLeft.empty()) {
        cursorLeft.pop_back();
    }
} 

B는 커서 왼쪽의 문자를 지우는 것이니까 왼쪽 deque가 비어있지 않을 때 pop_back 끝이다.

 

 

else if (order == "P") {
    char add;
    cin >> add;
    cursorLeft.push_back(add);
}

P가 입력됐다면 추가할 문자를 입력받고 왼쪽 deque에 push_back 해주면 된다.

 

while (!cursorLeft.empty()) {
    cout << cursorLeft.front();
    cursorLeft.pop_front();
}
while (!cursorRight.empty()) {
    cout << cursorRight.front();
    cursorRight.pop_front();
}

이제 왼쪽 deque부터 출력해주면 끝이다!!

 

 

무엇이 어려웠는가?

늘 느끼는 것처럼 자료구조를 선택하는 것이 어려웠다. 아직 연습이 많이 부족하다.

또, 문제 풀이의 방향을 잡는 것도 시간이 많이 걸렸다.

자료구조와 로직을 완벽하게 생각해낸 순간부터는 어려움 없이 간단하게 푼 구현 문제였다.

 

배운 점

 

문제를  읽고 생각해내는 직관적인 해결 방법도 중요하지만, 때로는 문제를 풀기 좋게 다른? 방식으로의 접근도 생각해봐야겠다고 생각했다.

  

 

시간 복잡도

먼저 입력받은 만큼 for문을 반복한다.

for문 안에 있는 연산들은 모두 O(1)의 시간 복잡도를 갖는다.

따라서 시간 복잡도는 O(n)이 된다.

 

 

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/1406.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.