[자료구조 기초 - 연결 리스트(LinkedList)]백준 에디터(1406번) 풀이 (C++/Python)

저번에는 ArrayList에 대해 알아봤습니다.

이번에는 LinkedList에 대해 알아보겠습니다.

 

ArrayList는 1-2-3-4-5-6처럼 주소값이 연속적으로 이어지는 동적 배열입니다.

그리고 조회 및 수정할 때 연속적인 index 기반이라서 O(1)의 시간 복잡도를 가지고 있습니다.

하지만 여기서 한계점이 있습니다.

0xA0	0xA1	0xA2	0xA3	0xA4	0xA5	0xA6	0xA7	0xA8	0xA9
0xA2	0xA8	1	2	3	4	5	6

현재 다음과 같이 저장되어 있습니다.

만약 맨 끝의 원소만 삭제한다고 하면 포인터 한 칸만 움직이면 되거든요.

그런데 만약 딱 중간에 있는 0xA4의 원소값을 없앨려고 하면 어떻게 해야 할까요?

그러면 매우 귀찮아지는 일이 벌어집니다.

*(0xA4) = *(0xA5);

*(0xA5) = *(0xA6);

*(0xA6) = *(0xA7);

이렇게 0xA4 뒤에 있는 모든 원소들의 값을 왼쪽으로 전부 다 옮겨야 하고 그 다음에 포인터를 옮겨야 하는 귀찮은 작업을 해야 합니다.

0xA0	0xA1	0xA2	0xA3	0xA4	0xA5	0xA6	0xA7	0xA8	0xA9
0xA2	0xA7	1	2	4	5	6	6

이렇게 바뀌어집니다.

이게 만약 리스트의 크기가 100000개이고 삭제되어야 하는 원소의 index가 0이라면?

그러면 99999개의 원소들을 모두 왼쪽으로 옮겨야 하는 O(N)의 시간 복잡도를 가지게 됩니다.

원소의 개수가 많아질 수록 비효율적입니다.

 

만약 조회/수정보다 추가/삭제가 압도적으로 많은 작업이라면 ArrayList는 오히려 독입니다.

이럴 때 나오는 것이 바로 LinkedList입니다.

			0xBC	---	0x3F
			12		24

ㅡ는 서로 연결되었다는 것을 의미합니다.

현재 두 원소가 서로 연결되어 있습니다.

0xBC의 오른쪽 간선은 0x3F와 연결되어 있고 0x3F의 왼쪽 간선은 0xBC와 연결되어 있습니다.

그리고 0xBC의 왼쪽 지점과 0x3F의 오른쪽 지점은 연결되지 않는 상태입니다.

 

여기서 두 지점 사이에 0x90(value는 18)를 넣고 싶습니다.

이럴 때 다음과 같은 과정을 거치면 됩니다.

			0xBC		0x3F
			12		24

먼저 두 지점의 연결을 해제해주세요.

			0xBC		0x90		0x3F
			12		18		24

그 다음 0x90을 불러옵니다.

			0xBC	ㅡ	0x90		0x3F
			12		18		24

그 다음 0xBC의 오른쪽 간선을 0x90에 연결하고 0x90의 왼쪽 간선을 0xBC와 연결합니다.

			0xBC	ㅡ	0x90	ㅡ	0x3F
			12		18		24

그 다음 0x90의 오른쪽 간선을 0x3F와 연결하고 0x3F의 왼쪽 간선을 0x90과 연결합니다.

이렇게 하면 12-24에서 18이 중간에 들어와서 12-18-24가 됩니다.

 

그러면 이번엔 반대로 원소 18을 제거할려면 어떻게 해야 할까요?

간단합니다. 추가 과정에서 역순으로 진행하면 됩니다.

그러면 바로 연결 해제됩니다.

자매품으로 아래와 같이 원형으로 만들 수도 있습니다.

	0xAB	ㅡ	0x7A	ㅡ	0x40
	1		2		3
	ㅣ				ㅣ
	0xF1				0x0E
	8				4
	ㅣ				ㅣ
	0x71	ㅡ	0x54	ㅡ	0xEE
	7		6		5

 

이렇게 해서 추가/삭제할 때 그 원소의 주소값이 무엇이든 O(1)의 시간 복잡도로 빠르게 가능합니다.

그런데 여기서 ArrayList는 조회/수정 대신 추가/삭제에서 느리다는 단점이 있잖아요?

LinkedList는 추가/삭제가 빠르지만 주소값이 불연속적이라 탐색하는 과정에서 느리다는 단점이 있습니다.

이로 인해 조회 및 수정하는 과정에서 O(N)의 시간 복잡도를 가집니다.

 

이제 아까 전에 했던 12, 24 사이에 18 원소를 추가하고 삭제하는 과정을 C언어로 구현해보겠습니다.

#include <stdio.h>
#include <stdlib.h>

// 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node* prev; // 왼쪽 사람의 손
    struct Node* next; // 오른쪽 사람의 손
} Node;

// 원형 이중 연결 리스트 구조체
typedef struct {
    Node* head; // 강강술래의 시작점 (기준점)
} CircularDoublyLinkedList;

// 1. 리스트 초기화
void initList(CircularDoublyLinkedList* list) {
    list->head = NULL;
}

// 2. 맨 뒤에 추가 (append) - 생성된 노드의 주소를 반환!
Node* insertEnd(CircularDoublyLinkedList* list, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;

    if (list->head == NULL) {
        // 첫 번째 노드일 경우: 혼자서 강강술래 (자기 자신을 가리킴)
        newNode->next = newNode;
        newNode->prev = newNode;
        list->head = newNode;
    } else {
        // 이미 사람이 있을 경우: 맨 마지막 사람(tail)을 찾아서 연결
        Node* tail = list->head->prev; // 원형이므로 head의 이전은 항상 tail!

        tail->next = newNode;       // 기존 마지막 사람의 오른손을 새 사람에게
        newNode->prev = tail;       // 새 사람의 왼손을 기존 마지막 사람에게
        newNode->next = list->head; // 새 사람의 오른손을 첫 사람(head)에게
        list->head->prev = newNode; // 첫 사람의 왼손을 새 사람에게
    }
    return newNode; // ★ 중요: 생성된 노드의 '주소값(GPS)'을 반환합니다.
}

// 3. 특정 노드의 '바로 뒤'에 추가 (O(1) 삽입)
Node* insertAfter(Node* target, int value) {
    if (target == NULL) return NULL;
    
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;

    Node* nextNode = target->next; // target의 원래 오른쪽 사람

    // 새 사람(18)과 양옆 사람(12, 24)의 손을 연결합니다.
    newNode->prev = target;
    newNode->next = nextNode;
    
    target->next = newNode;
    nextNode->prev = newNode;

    return newNode; // 캐싱을 위해 주소값 반환
}

// 4. 주소값을 이용한 즉시 삭제 (O(1) 삭제)
void deleteNode(CircularDoublyLinkedList* list, Node* target) {
    if (list->head == NULL || target == NULL) return;

    // 만약 지우려는 노드가 리스트의 유일한 노드라면?
    if (target->next == target) {
        list->head = NULL;
    } else {
        Node* leftPerson = target->prev;
        Node* rightPerson = target->next;

        // 타겟을 왕따(?)시키고 양옆 사람끼리 손을 잡게 합니다.
        leftPerson->next = rightPerson;
        rightPerson->prev = leftPerson;

        // 만약 지운 노드가 head였다면, 다음 사람에게 head 자리를 물려줍니다.
        if (list->head == target) {
            list->head = rightPerson;
        }
    }
    // 다 쓴 노드의 메모리 반환
    free(target);
}

// 전체 출력 함수
void printList(CircularDoublyLinkedList* list) {
    if (list->head == NULL) {
        printf("현재 리스트: []\n");
        return;
    }
    
    Node* current = list->head;
    printf("현재 리스트: [ ");
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != list->head); // 다시 head로 돌아올 때까지 반복
    printf("]\n");
}

int main() {
    CircularDoublyLinkedList list;
    initList(&list);

    printf("=== 1단계 : 12 삽입 ===\n");
    Node* node12 = insertEnd(&list, 12); // 나중에 쓰기 위해 주소를 저장(캐싱)
    printList(&list);

    printf("\n=== 2단계 : 24 삽입 ===\n");
    insertEnd(&list, 24);
    printList(&list);

    printf("\n=== 3단계 : 12와 24 사이에 18 삽입 ===\n");
    // 처음부터 찾을 필요 없이, 아까 저장한 node12의 '바로 뒤'에 삽입!
    // 동시에 18의 주소값도 캐싱해둡니다.
    Node* cached_node_18 = insertAfter(node12, 18);
    printList(&list);

    printf("\n=== 4단계 : 캐시를 활용한 18 삭제 (탐색 시간 O(1)) ===\n");
    // 반복문(for/while)으로 18을 찾는 과정이 전혀 없습니다!
    deleteNode(&list, cached_node_18);
    printList(&list);

    return 0;
}

네... 이해 못 해도 됩니다.

출력 결과는 다음과 같이 나옵니다.

더 빠른 탐색을 위해 캐시 기능을 사용했지만 ArrayList이면 캐시 기능 없이도 빠른 조회가 가능합니다.

이것을 통해 LinkedList는 엄청 빠른 추가/삭제를 해서 "일단 데이터를 무작정 많이 집어넣자!"라고 할 때 큰 도움이 됩니다.

ArrayList로 할 때 메모리를 연속적으로 할당해야 해서 정말 많은 데이터를 추가해야 할 때 메모리가 부족해지는 문제점이 발생합니다.

예시로 남은 메모리 부분이 o이고 이미 할당된 부분이 x라고 가정합니다.

그리고 현재 데이터 3개를 넣어야 합니다.

메모리가 만약 xoxoxoxoxoxoxoxo 상태이면 분명히 메모리 남은 칸이 8칸인데도 불구하고 ArrayList이면 할당할 수 없는 문제점이 발생합니다.

하지만 LinkedList라면 xoxoxoxoxoxoxoxo라도 데이터를 구겨넣을 수 있어 메모리 효율이 좀 더 좋아집니다.

물론 탐색을 빨리 할려면 LinkedList가 아닌 ArrayList로 해야 합니다.

 

그래서 보통 데이터를 다음과 같이 처리합니다.

1. 초반에 데이터를 추가할 때 LinkedList로 합니다. 그러면 최대한 많이 채워 넣을 수 있습니다.

2. LinkedList로 순차 탐색을 딱 1번만 합니다. 거기서 불필요한 데이터를 순식간에 제거합니다.

3. 1번 과정과 2번 과정을 반복하여 메모리 안에 품질 좋은 데이터를 최대한 많이 채워 넣을 수 있습니다.

4. 이제 더 큰 용량의 메모리로 옮겨서 각 데이터 별로 ArrayList를 통해 구분 및 정리해서 조회 및 탐색하기 딱 좋게 만듭니다.

이렇게 해서 대용량 데이터를 효율적으로 관리할 수 있습니다.

 

이제 백준 문제로 넘어갈까요???

 

 

문제 : 에디터(1406번)(Silver II)

문제 링크 : https://www.acmicpc.net/problem/1406
출처 : Baekjoon Online Judge

 

실버 2티어 수준이면 코딩 테스트에 나올 정도로 좀 어려운 문제입니다.

거기에 LinkedList로 추가/삭제는 그렇다 쳐도 마지막에 O(1) 시간 복잡도의 조회까지 필요해서 정말 막막할 것입니다.

하지만 걱정마십시오. 이 문제는 편법을 사용해서 해결할 수 있습니다.

ArrayList 2개이면 이 문제를 정말 쉽게 해결할 수 있거든요.

이름이 left, right인 ArrayList로 어떻게 해결할 수 있을까요?

각 테스트 케이스들을 하나씩 뜯어보면서 이 문제를 해결해보겠습니다.

 

[테스트 케이스 1]

문자열 "abcd"가 나왔습니다.

가장 1번째로 "abcd"를 문자로 쪼개고 모두 다 left에 넣는 것입니다.

left = [a, b, c, d], right = []

그 다음 명령어 수가 3개이며 각각 "P x", "L", "P y"가 나왔습니다.

각 명령어들을 순서대로 진행합니다.

(1번째 명령어)

현재 커서는 abcd_이며 여기서 _는 커서입니다.

커서 왼쪽에 x를 추가합니다. 즉, abcd(x_) -> abcdx_가 됩니다.

left 리스트에 x를 추가합니다.

left = [a, b, c, d, x], right = []

(2번째 명령어)

커서를 왼쪽으로 옮깁니다.

그러면 abcd_x가 됩니다.

이 때 x는 left에서 빼고 right로 옮깁니다.

left = [a, b, c, d], right = [x]

(3번째 명령어)

커서 왼쪽에 y를 추가합니다.

이러면 abcd(y_)x -> abcdy_x가 됩니다.

이 때 left에 y를 추가합니다.

left = [a, b, c, d, y], right = [x]

(결과)

abcdyx가 됩니다.

 

[테스트 케이스 2]

문자열 "abc"가 나왔습니다.

그러므로 left = [a, b, c]가 되며 현재 커서는 abc_입니다.

각 명령어들을 수행하겠습니다.

(1번째 명령어)

커서를 왼쪽으로 옮깁니다.

그러면 ab_c가 되며 left = [a, b], right = [c]가 됩니다.

(2번째 명령어)

커서를 왼쪽으로 옮깁니다.

그러면 a_bc가 되며 left = [a], right = [c, b]가 됩니다.

(3번째 명령어)

커서를 왼쪽으로 옮깁니다.

그러면 _abc가 되며 left = [], right = [c, b, a]가 됩니다.

(4번째 명령어)

커서를 왼쪽으로 옮깁니다.

그런데 커서 왼쪽에는 문자가 더이상 없습니다.

그러므로 아무런 변화가 없으며 left = [], right = [c, b, a]입니다.

(5번째 명령어)

커서를 왼쪽으로 옮깁니다.

그런데 커서 왼쪽에는 문자가 더이상 없습니다.

그러므로 아무런 변화가 없으며 left = [], right = [c, b, a]입니다.

(6번째 명령어)

커서 왼쪽에 x를 추가합니다.

그러므로 x_abc가 되며 left = [x], right = [c, b, a]가 됩니다.

(7번째 명령어)

커서를 왼쪽으로 옮깁니다.

그러면 _xabc가 되며 left = [], right = [c, b, a, x]가 됩니다.

(8번째 명령어)

커서 왼쪽에 있는 문자 1개를 삭제합니다.

그런데 커서 왼쪽에는 문자가 없습니다.

그러므로 아무런 변화가 없으며 left = [], right = [c, b, a, x]입니다.

(9번째 명령어)

커서 왼쪽에 y를 추가합니다.

그러므로 y_xabc가 되며 left = [y], right = [c, b, a, x]가 됩니다.

(결과)

최종적으로 left에서는 순서대로 읽어서 y, right에서는 역순으로 읽어서 xabc가 나와서 yxabc가 됩니다.

 

[테스트 케이스 3]

문자열 "dmih"가 나왔습니다.

초기 상태는 dmih_이며 left = [d, m, i, h]입니다.

(1번째 명령어)

커서 왼쪽에 있는 문자 1개를 삭제합니다.

dmi_

left = [d, m, i], right = []

(2번째 명령어)

커서 왼쪽에 있는 문자 1개를 삭제합니다.

dm_

left = [d, m], right = []

(3번째 명령어)

커서 왼쪽에 x를 추가합니다.

dmx_

left = [d, m, x], right = []

(4번째 명령어)

커서를 왼쪽으로 옮깁니다.

dm_x

left = [d, m], right = [x]

(5번째 명령어)

커서 왼쪽에 있는 문자 1개를 삭제합니다.

d_x

left = [d], right = [x]

(6번째 명령어)

커서 왼쪽에 있는 문자 1개를 삭제합니다.

_x

left = [], right = [x]

(7번째 명령어)

커서 왼쪽에 있는 문자 1개를 삭제합니다.

하지만 커서 왼쪽에 문자가 없어서 아무런 변화가 없습니다.

_x

left = [], right = [x]

(8번째 명령어)

커서 왼쪽에 y를 추가합니다.

y_x

left = [y], right = [x]

(9번째 명령어)

커서를 오른쪽으로 옮깁니다.

yx_

left = [y, x], right = []

(10번째 명령어)

커서를 오른쪽으로 옮깁니다.

하지만 커서 오른쪽에 문자가 없어서 아무런 변화가 없습니다.

yx_

left = [y, x], right = []

(11번째 명령어)

커서 왼쪽에 z를 추가합니다.

yxz_

left = [y, x, z], right = []

(결과)

yxz가 됩니다.

 

자, 이제 이것을 C++로 구현하겠습니다.

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

vector<char> L;
vector<char> R;

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

    string s;
    cin >> s;

    int size = s.size();

    for(int i = 0; i < size; i++) L.push_back(s[i]);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++) {
        char cmd;
        cin >> cmd;

        switch(cmd) {
            case 'L' :
                if(!L.empty()) {
                    char ch = L.back();
                    L.pop_back();
                    R.push_back(ch);
                }
                break;
            case 'D' :
                if(!R.empty()) {
                    char ch = R.back();
                    R.pop_back();
                    L.push_back(ch);
                }
                break;
            case 'B' :
                if(!L.empty()) L.pop_back();
                break;
            case 'P' :
                char ch;
                cin >> ch;
                L.push_back(ch);
                break;
            default :
                break;
        }
    }

    int L_size = L.size();
    int R_size = R.size();

    for(int i = 0; i < L_size; i++) cout << L[i];
    for(int i = R_size - 1; i > -1; i--) cout << R[i];

    return 0;
}

back()으로 맨 마지막 원소를 저장하고 pop_back()을 합니다.

왜냐면 C++에서 pop_back()의 반환값이 void라서 삭제 전 값을 따로 저장해야 합니다.

 

이제 같은 논리를 바탕으로 Python으로 구현해보겠습니다.

import sys

input = sys.stdin.readline

left:list = list(input().rstrip())
right:list = []

N:int = int(input().rstrip())

for _ in range(N) :
    L:list = list(map(str, input().split()))
    command:list = L[0]
    if command == "L" :
        if left :
            right.append(left.pop())
    if command == "D" :
        if right :
            left.append(right.pop())
    if command == "B" :
        if left :
            left.pop()
    if command == "P" :
        left.append(L[1])
        
result:str = ''.join(map(str, left)) + ''.join(map(str, right[::-1]))
print(result)