반응형

문제 출처 :


https://www.acmicpc.net/problem/5397



알고리즘 분석 :


문제 해결에 필요한 사항

1. 이중 연결 리스트에 개념 이해

2. 이중 연결 리스트 문제 접목


솔직히 이 문제는 사실 이중 연결 리스트로 풀지 않아도 된다.


스택을 2개 이용해도 풀 수 있다 생각이 든다. 

('<'는 pop로 잠시 빼주고 '-'는 pop을하고 등등의 방식으로..)


하지만, 이 문제를 보는 순간 이중 연결 리스트로 순수하게 제작해 보고 싶은 마음에 한번 해 보았다.


알고리즘 측면에서는 다소 부족할 수 있지만, 자료구조 측면에서는 이중 연결 리스트 같은 개념을 가지고


언제 응용 해 볼수 있을지 이 문제를 통해 다시 한번 생각해 보았으면 한다.


주석을 통해 알고리즘에 대한 내용은 모두 담아두었다.



소스 코드 : 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
char arr[1000001];
int i = 0;
 
typedef struct _Node
{
    char s;
    struct _Node *next;
    struct _Node *prev;
}Node;
 
typedef struct _List
{
    Node *first;
    Node *last;
    Node *cur;
}List;
 
void init(List *list)
{
    // Create dummy node
    // init 후 생성되는 모습 
    // f,c  l
    // ㅁ---ㅁ
    Node *newnodeF = (Node*)malloc(sizeof(Node)); // 앞쪽 더미 노드
    Node *newnodeL = (Node*)malloc(sizeof(Node)); // 뒤쪽 더미 노드
 
    newnodeF->next = newnodeL;
    newnodeF->prev = NULL;
    newnodeF->= NULL;
 
    newnodeL->next = NULL;
    newnodeL->prev = newnodeF;
    newnodeF->= NULL;
 
    list->first = newnodeF;
    list->last = newnodeL;
    list->cur = newnodeF;
}
 
void next(List *list)
{
    /* '<' 를 받으면
     * 왼쪽으로 한칸 옮기기 전, 아무것도 없는지 혹은 문자가 있는 첫 노드인지 확인한다.  
     * 이동 방식은 현재 위치를 가리키는 cur을 왼쪽으로 한칸 옮긴다.
     */
    if (arr[i] == '<')
    {
        if (list->cur->prev != list->first || list->cur == list->first->next)
        {
            if (list->cur != list->first)
                list->cur = list->cur->prev;
        }
    }
 
    /* '>' 를 받으면
    * 오른쪽으로 한칸 옮기기 전, 아무것도 없는지 혹은 문자가 있는 마지막 노드인지 확인한다.
    * 이동 방식은 현재 위치를 가리키는 cur을 오른쪽으로 한칸 옮긴다.
    */
    else if (arr[i] == '>')
    {
        if (list->cur->next != list->last)
        {
            if (list->cur != list->last)
                list->cur = list->cur->next;
        }
    }
 
    /* '-' 를 받으면
    * cur에 해당하는 노드를 삭제한다. 이때 삭제하기전, cur에 대한 정보가 필요하므로
    * 삭제할 노드는 tmp에 담아 삭제한다.
    * 삭제 방식은 지우는 노드의 좌 우 노드를 연결 한 후 삭제해야한다.
    */
    else if (arr[i] == '-')
    {
        if (list->cur->!= NULL)
        {
            Node *tmp = list->cur;
 
            // 지우는 노드의 양 좌 우 노드를 연결해준다.
            list->cur->next->prev = list->cur->prev;
            list->cur->prev->next = list->cur->next;
 
            list->cur = list->cur->prev;
            free(tmp);
        }
    }
 
    /* 그 외에 문자를 받으면 노드를 생성하여 이어준다.
    * 잇는 방식은 newnode를 먼저 이어주고 난 뒤,
    * 기존에 존재하던 노드를 이어준다.
    */
    else
    {
        Node *newnode = (Node*)malloc(sizeof(Node));
 
        newnode->prev = list->cur;
        newnode->next = list->cur->next;
 
        newnode->= arr[i];
 
        list->cur->next->prev = newnode;
        list->cur->next = newnode;
        list->cur = newnode;
    }
    i++;
}
 
void print(List *list)
{
    // 처음부터 끝까지 출력을 한다.
    list->cur = list->first->next;
 
    while (list->cur != list->last)
    {
        printf("%c", list->cur->s);
        list->cur = list->cur->next;
    }
    printf("\n");
 
    // 출력 후 free를 통해 다음 테스트 케이스를 받을 준비를 한다.
    list->cur = list->first;
 
    while (list->cur != list->last)
    {
        Node *tmp = list->cur;
 
        list->cur = list->cur->next;
        free(tmp);
    }
    free(list->last);
    i = 0// i 초기화(배열 번호에 이용)
}
 
 
int main()
{
    int len;
    int n;
 
    scanf("%d"&n);
 
    for (int i = 0; i < n; i++)
    {
        List list;
        scanf("%s", arr);
 
        len = strlen(arr);
 
        // 더미 노드를 만들어 첫 노드와 끝 노드의 삽입 삭제를 편리하게 한다.
        init(&list);
 
        for (int i = 0; i < len; i++)
            next(&list);
 
        print(&list);
 
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[Programmers] 섬 연결하기  (0) 2019.10.23
[3780번] Corporative Network  (0) 2019.10.17
[1248번] 공통조상  (0) 2019.09.27
[Programmers] 저울  (0) 2019.09.10
[1249번] 보급로  (0) 2019.09.09