[ 백준 1406 ] 에디터

안녕하세요 !!! 우디 ✨ 입니다 .

---

 

문제

백준 에디터 문제

 

문제 설명

저는 이중 연결 리스트 ( Doubly Linked List ) 로 풀었습니다.

 

먼저, 헤드 노드를 이용하여 리스트에 접근할 수 있게 만들어 주었습니다.

문제에서의 cursor는 노드를 가르키는 포인터 변수를 따로 만들어 주었습니다.

( 그 이유는 헤드노드를 cursor의 역할로 할 수도 있겠지만, 그렇게 되버리면 나중에 답을 출력할때 순서가 꼬이게 됩니다 . )

 

 

위의 그림처럼 실제 cursor의 위치는 연결리스트 에서는 cursor의 오른쪽 문자가 들어있는 노드를 가르키게 했습니다. 즉, 노드를 가르키는 cursor의 위치는 실제로 cursor가 가르키고 있는 문자 왼쪽에 위치하게 됩니다.

 

이를 이용하여 P $를 처리할 함수와 문자열 입력값을 받아 연결리스트를 만들어 주는 과정을 통일시켰습니다 !

 

작성해야 할 함수들

• 노드 동적 생성 함수
• L (왼쪽으로 이동) -- > 더이상 갈 곳 없으면 무시
• D (오늘쪽으로 이동) -- > 더이상 갈 곳 없으면 무시
• B ( 왼쪽 삭제 ) -- > 삭제할 것이 없으면 무시 , 노드 동적할당 받았으면 삭제될 노드 꼭 해제
• P $ ( 왼쪽에 $(문자는 랜덤) 추가 ) -- > cursor노드 앞에 문자 노드 추가

 

구현 ( 주석 설명 O )

​x
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
using namespace std;
​
typedef struct ListNode {
    char data;
    struct ListNode *rlink;
    struct ListNode *llink;
}ListNode;
​
//노드 동적 생성
ListNode *create_node(char item, ListNode *rlink, ListNode *llink)
{
    ListNode *new_node;
    new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->data = item;//왜 string으로 하면 안드가냥
    new_node->rlink = new_node;
    new_node->llink = new_node;
    return (new_node);
}
​
//헤드 노드 초기화
void init(ListNode *head)
{
    head->rlink = head;
    head->llink = head;
}
​
// P $
void insert(ListNode *b, ListNode *new_node)
{// b : 삽입될 노드의 선행 노드
    new_node->llink = b->llink;
    new_node->rlink = b;
    b->llink->rlink = new_node;
    b->llink = new_node; // 순서에 유의하기
}
​
// L
ListNode *leftt(ListNode *head, ListNode *cur)
{
    if (cur->llink != head)
        cur = cur->llink;
    return cur;
}
​
// D
ListNode *rightt(ListNode *head, ListNode *cur)
{
    if (cur != head)
        cur = cur->rlink;
    return cur;
}
​
// B
void erase(ListNode *head, ListNode *cur)
{
    ListNode *removed;
    removed = cur->llink;//cur(sor)의 앞의 노드가 삭제되니 !
    if (cur != head->rlink)//왼쪽 끝까지 옴
    {
        cur->llink->llink->rlink = cur;
        cur->llink = cur->llink->llink;
        free(removed);//해제 꼭 해줘야해요 !!!
    }
}
​
void print(ListNode *head)
{
    ListNode *p = head;
    ListNode *removed;
    for (p = head->rlink; p != head;p=p->rlink)
    {
        printf("%c", p->data);
    }
    cout << endl;
}
​
int main()
{
    ListNode head_node;
    init(&head_node);
​
    char n[200000];
    int m;
​
    scanf("%s", n);//^^ cin 느려요 ..
    cin >> m;
    //노드 연결
    for (int i = 0; n[i]!=0; i++)
        insert(&head_node, create_node(n[i], NULL, NULL));//입력값 문자열                                                       //연결 리스트 만들어 주기 
​
    ListNode *cursor = &head_node;
​
    char dir;
    for (int i = 0; i < m; i++)
    {
        scanf(" %c", &dir);
        if (dir == 'L')
            cursor = leftt(&head_node, cursor);
        else if (dir == 'D')
            cursor = rightt(&head_node, cursor);
        else if (dir== 'B')
            erase(&head_node, cursor);
        else
        {
            scanf(" %c", &dir);
            insert(cursor, create_node(dir, NULL, NULL));
        }
    }
    print(&head_node);//정답
}