바킹독 0x04 문제1 - / 백준 1406번 에디터

 

연결리스트이다.

배열과의 차이점이 명확했다.

배열은 중간에 숫자를 넣으려면 O(N)이지만

연결리스트는 O(1)이라고 한다.

 

자료구조를 오랜만에 보니 기분이 새롭다.

 

문제를 한번 같이 보자!

---

안 보고 싶어졌다.

 

문제가 너무 길다.

글자수가 600,000 자라는 것 그리고 왼쪽 위

0.3초 ( 하단 참고)라고 되어있는 것으로 볼 때

 

배열은 쓰지 못한다는 말을 하려는 거 같았다.

문제를 일단 해석하자.

.... 어.. 오

너무.. 길어요 선생님..

 

문자열이 주어지고 N / 명령어의 개수 M

흠.. 오.....

아...

어렵다.

 

 

P x를 cin으로 받아낼 수가 있나? 그러면 p일 경우.. 에 대해서 if문을 걸어줘야 하나?

영상에서.. 다 구현하고 오라고 하셨는데...........

....... 엄...

ㅇㅅㅇ

못할 정도는 아니라고 하셨는데..

...

 

하셨는데...

어렵다. 어렵다.

 

답을 보고도 이해를 못 해서 지피티한테 물어보며..

코드를 한줄한줄 분석했다.

 

답은 이렇다.

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

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

    string N;
    cin >> N;

    list<char> L;
    for (auto c : N)
        L.push_back(c);
    auto cursor = L.end();

    int M;
    cin >> M;

    while (M--)
    {
        char order;
        cin >> order;

        if (order == 'P')
        {
            char add;
            cin >> add;
            L.insert(cursor, add);
        }
        else if (order == 'L')
        {
            if (cursor != L.begin())
            {
                cursor--;
            }
        }
        else if (order == 'D')
        {
            if (cursor != L.end())
            {
                cursor++;
            }
        }
        else
        {
            if (cursor != L.begin())
            {
                cursor--;
                cursor = L.erase(cursor);
            }
        }
    }
    for (auto c : L)
        cout << c;
}

 

아니.. 다 캡처하려니.. 스크롤을 내려야 해서 이왕 이렇게 된 거

조금조금 캡처하기로 했다!

시작하고 N 문자열 받기

 

list <char> L;

보통 연결리스트여서 대중적으로 L을 많이 쓰는 거 같다.

그리고 문제에서도 L이라고 나와있다.

 

리스트를 만들어 두고

N을 받은 문자열을

for ( auto c : N ) L.push_back(c);

 c에다가 한 글자씩 넣고, 맨뒤에 한글자씩 추가하게 된다.

 

다음에 cursor을 설정해줘야 한다.

커서는 일단 기본이 맨 뒤에 있어줘야 하기 때문에

auto cursor = L.end() 해줘야 한다.

두 번째로 받을 숫자는 M 명령어 개수이기 때문에

int로 하고 cin 해준다.

다음에 그 횟수만큼 돌려야 하기 때문에

while (M--)라고 해줘야 한다고 한다.

 

그다음은 이제 L D P 이런 친구 들이라서

char하나 받아준다.

char order; cin >> order;

 

그다음에 order의 값을 if문으로 해서 받으면 된다.

 

 < L일 경우 >

커서를 왼쪽으로 이동시키기 때문에

커서의 값을 빼주면 된다.

단, 위에도 적혀있지만 맨 앞에 있는 경우 무시하라고 했으니

if ( cursor != L.begin()) cursor--;

예외사항을 써줘야 한다.

커서가 맨 앞에 있을 경우엔 앞이 없으니까!

 

 < D일 경우 >

커서를 오른쪽으로 이동시킬 테니

위에랑 반대로 맨 뒤에서는 무시해줘야 한다.

if ( cursor != L.end()) cursor++;

 

< P일 경우 >

숫자로 보이지만 위에 문제를 읽어보면  $이 값 또한 문자라고 적혀있다.

.. 와 이렇게 세밀하게 봐야 하다니..ㄷㄷ

여하튼 그래서 char로 받는다.

char add; cin >> add;
L.insert(cursor, add);

insert의 경우 커서가 가리키는 원소 앞 즉 왼쪽에 값을 삽입하기 때문에

맨 앞에 둘 때는 문제가 안된다.

 

< B일 경우 >

마지막으로 삭제이다.

삭제의 경우 커서의 왼쪽에 있는 문자를 삭제하라고 했기 때문에

맨 왼쪽의 경우 = 처음일 때는 제외해줘야 한다!

 

그래서 또 제외를 해주고

 if (cursor != L.begin())     cursor--;     cursor = L.erase(cursor);

 

커서를 왼쪽으로 이동후 ( cursor-- )

 

erase 삭제인데

 

 erase의 경우 괄호 안에 있는 값이 가리키는 값을 제거하고,

삭제된 원소의 다음 원소를 가리키는 iterator( 없으면 end() )를 반환한다. 

단순하게, 커서의 위치 왼쪽을 지우라 했으니

cursor--해주고 erase 해준 거라고 이해하면 될 거 같다..

 

그리고 중요한것!

그 위치의 값을 지우고나면 erase는 커서 위치값을 반환하기 때문에

커서의 위치를 꼭 넣어주어야한다.

cursor = L.erase(cursor);

 

어렵다.

그다음에 마지막 문장을 출력해줘야 하니까

for ( auto c : L ) cout << c ;

 

해주면 된다.

 

후...

안 보고 하려니까 한 번씩 실수하는 게 있었다.

erase에서 cursor--; 이것도 if문에 안 넣고

가장 중요한 cursor도 사실 선언도 안 해줬었다..ㅋㅋ 스읍..

 

제일 헷갈렸던 건 erase였다.

다음칸으로 이동하는 것도 헷갈리고

지운다는 게 진짜 커서를 생각했나

왼쪽 오른쪽이 헷갈렸다.

 

그래서 투명문자열이라고 생각하기로 했다.

지피티한테 여러 번 물어봤지만

제대로 된 확실한 비유를 알려주지 않았다...

 

내가 그만큼 잘 이해 못 한 거겠지.. 쩝

 

그 자리에 있는 거 지우고 다음칸으로 이동하기

확실히 하자!!