21W25-List

[moodmine]

SWEA 1228. 암호문 1

SWEA 1229. 암호문 2

SWEA 1230. 암호문 3

암호문 1, 2 모두 같은 코드로 풀음.

레퍼런스 코드가 연결 리스트라 하지만 힙배열때문에 배열리스트나 다름 없어서 동적배열을 이용해서 수정을 하든 처음부터 다시 만들든 해야함.

위치가 0으로 주어질 때를 위해 더미 리스트로 만드는 것을 추천.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int MAX_NODE;

typedef struct listNode
{
    int data;
    struct listNode* prev;
    struct listNode* next;
} ListNode;

void initListNode(ListNode* node)
{
    node->data = 0;
    node->prev = node;
    node->next = node;
}

ListNode* appendListNode(ListNode* list, int data)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    initListNode(node);
    node->data = data;

    if (list == NULL)
    {
        return node;
    }
    else
    {
        ListNode* last = list->prev;
        last->next = node;
        list->prev = node;
        node->prev = last;
        node->next = list;
        return list;
    }
}

ListNode* removeListNode(ListNode* list)
{
    if (list == list->next)
    {
        return list;
    }
    else
    {
        ListNode* prev = list->prev;
        ListNode* next = list->next;
        free(list);
        prev->next = next;
        next->prev = prev;
        return next;
    }
}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    //freopen("input.txt", "r", stdin);
    //cin >> T;
    T = 10;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d", &MAX_NODE);

        ListNode* list = NULL;
        ListNode* node;

        list = appendListNode(list, NULL);

        int data;

        for (int i = 0; i < MAX_NODE; i++)
        {
            scanf("%d", &data);
            list = appendListNode(list, data);
        }

        ListNode* LastNode;
        LastNode = appendListNode(list, NULL);

        int MAX_COMMAND;

        scanf("%d", &MAX_COMMAND);
        char command;
        int cur;
        int num_co;

        for (int i = 0; i < MAX_COMMAND; i++)
        {
            getchar();
            scanf("%c", &command);
            switch (command)
            {
            case 'I':
                scanf("%d %d", &cur, &num_co);
                node = list->next;
                for (int j = 0; j < cur; j++) // 위치가 다를 시 수정
                {
                    node = node->next;
                }
                for (int j = 0; j < num_co; j++)
                {
                    scanf("%d", &data);
                    node = appendListNode(node, data);
                }
                break;

            case 'D':
                scanf("%d %d", &cur, &num_co);
                node = list->next;
                for (int j = 0; j < cur; j++)
                {
                    node = node->next;
                }
                for (int j = 0; j < num_co; j++)
                {
                    node = removeListNode(node);
                }
                break;

            case 'A':
                scanf("%d", &num_co);
                node = LastNode;
                for (int j = 0; j < num_co; j++)
                {
                    scanf("%d", &data);
                    node = appendListNode(node, data);
                }
                break;
            }
        }

        printf("#%d", test_case);
        node = list->next;
        for(int i = 0; i < 10; i++)
        {
            printf(" %d", node->data);
            node = node->next;
        }
        printf("\n");
    }
    return 0;
}

[moodmine]

레퍼런스 코드 부연 설명

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define MAX_NODE 100 // 최대 생성 가능한 노드 *링크드 리스트인데, 최대 노드들 정해놓는 게 이상함 -> 수정 혹은 새로 만드는 것이 필요

typedef struct listNode // 노드 구조체 선언
{
    int data;
    struct listNode* prev;
    struct listNode* next;
} ListNode;

typedef struct  // 노드 힙에 대한 구조체 정의 * 힙에는 각 배열의 사용여부와 노드에 대한 정보가 들어가 있음
{
    int use;
    ListNode node;
} ListNodeHeap;

ListNodeHeap heap[MAX_NODE]; // 리스트 노드 힙 선언

void initHeap(void) // 힙 초기화 함수
{
    int i;
    for (i = 0; i < MAX_NODE; i++)
    {
        heap[i].use = 0;
    }
}

void initListNode(ListNode* node) // 노드 초기화 함수
{
    node->data = 0;
    node->prev = node;
    node->next = node;
}

ListNode* getListNode(void) // 빈 노드 힙을 찾아 비어있는 힙에 노드를 할당하는 함수
{
    int i;
    for (i = 0; i < MAX_NODE; i++) // 사용하지 않는 노드 힙을 찾는 반복문
    {
        if (!heap[i].use)
        {
            heap[i].use = 1;
            initListNode(&heap[i].node);
            return &heap[i].node;
        }
    }
    return NULL;
}

void destroyListNode(ListNode* node) // 노드를 제거하는 함수
{
    ListNodeHeap* heap_node = (ListNodeHeap*)((int*)node - 1); // 힙 배열 요소 주소 값
    heap_node->use = 0;
}

ListNode* appendListNode(ListNode* list, int data) // 노드를 삽입하는 함수
{
    ListNode* node = getListNode(); // 힙에 노드를 할당
    node->data = data;
    if (list == NULL)
    {
        return node;
    }
    else
    {
        ListNode* last = list->prev;
        last->next = node;
        list->prev = node;
        node->prev = last;
        node->next = list;
        return list;
    }
}

ListNode* removeListNode(ListNode* list, ListNode* node) // 노드를 삭제하는 함수
{
    if (list == list->next)
    {
        destroyListNode(node);
        return NULL;
    }
    else
    {
        ListNode* prev = node->prev;
        ListNode* next = node->next;
        prev->next = next;
        next->prev = prev;
        destroyListNode(node);
        return (list == node) ? next : list;
    }
}

[murry2018]

SWEA 1228. 암호문 1

SWEA 1229. 암호문 2

SWEA 1230. 암호문 3

#include <cstdio>

using namespace std;

typedef struct cons cons;

cons* global_tail = nullptr;

struct cons {
  int car;
  cons* cdr;
  cons(int car, cons *cdr): car(car), cdr(cdr) {};
  int nth(int n) {
    cons* pcon = this;
    for (int i = 0; i < n; i++) {
      pcon = pcon->cdr;
    }
    return pcon->car;
  }
  cons* nth_cons(int n) {
    cons* pcon = this;
    for (int i = 0; i < n; i++) {
      pcon = pcon->cdr;
    }
    return pcon;
  }
  void destroy() {
    cons* pcon = this;
    while (pcon != nullptr) {
      cons* rest = pcon->cdr;
      delete pcon;
      pcon = rest;
    }
  }
};

int len(cons* list) {
  cons* pcon = list;
  int i = 0;
  while (pcon != nullptr) {
    pcon = pcon->cdr;
    i++;
  }
  return i;
}

cons* append(cons* list, cons* head, cons* tail);

// for global instance
// start in [-1, inf)
cons* insert(cons* list, int start, cons* head, cons* tail) {
  if (start == -1) {
    tail->cdr = list;
    return head;
  }

  cons* pcon = list->nth_cons(start);
  if (pcon == nullptr) {
    return append(list, head, tail);
  }

  cons* rest = pcon->cdr;
  if (rest == nullptr) {
    global_tail = tail;
  }
  pcon->cdr = head;
  tail->cdr = rest;
  return list;
}

//for global instance
cons* remove(cons* list, int start, int n) {
  if (n <= 0)
    return list;
  if (start == -1) {
    cons* del_head = list;
    cons* del_tail = del_head->nth_cons(n-1);
    list = del_tail->cdr;
    del_tail->cdr = nullptr;
    del_head->destroy();
    return list;
  }
  cons* front_del_head = list->nth_cons(start);
  cons* del_head = front_del_head->cdr;
  cons* del_tail = del_head->nth_cons(n-1);
  if (del_tail == nullptr || del_tail->cdr == nullptr) {
    global_tail = front_del_head;
    front_del_head->cdr = nullptr;
  } else {
    front_del_head->cdr = del_tail->cdr;
    del_tail->cdr = nullptr;
  }
  del_head->destroy();
  return list;
}

// for global instance
cons* append(cons* list, cons* head, cons* tail) {
  if (list == nullptr) {
    return head;
  }
  if (global_tail == nullptr) {
    global_tail = tail;
    return list;
  }
  global_tail->cdr = head;
  global_tail = tail;
  return list;
}

// list IO function
// doesn't modify global instance
cons* read_list(int length, cons **ptail) {
  int item;
  cons *new_head = nullptr, *new_tail = nullptr;
  for (int i = 0; i < length; i++) {
    scanf("%d", &item);
    cons *node = new cons(item, nullptr);
    if (new_head == nullptr) { // implies new_tail == nullptr
      new_head = node;
    } else {
      new_tail->cdr = node;
    }
    new_tail = node;
  }
  if (ptail != nullptr) {
    *ptail = new_tail;
  }
  return new_head;
}

// list IO function
// doesn't depend on global instance
void dump_list(cons *list, int throttle) {
  cons* pcon = list;
  static char* middle = (char*)"";
  while (pcon != nullptr) {
    middle = (char*)" ";
    printf("%s%d", middle, pcon->car);
    pcon = pcon->cdr;
    if (--throttle == 0) {
      break;
    }
  }
}

cons* interpret_insert(cons* list) {
  int x, y;
  scanf("%d %d", &x, &y);
  if (y <= 0)
    return list;
  cons *new_head = nullptr, *new_tail = nullptr;
  new_head = read_list(y, &new_tail);
  return insert(list, x-1, new_head, new_tail);
}

cons* interpret_delete(cons* list) {
  int x, y;
  scanf("%d %d", &x, &y);
  if (y <= 0)
    return list;
  return remove(list, x-1, y);
}

cons* interpret_add(cons* list) {
  int y;
  scanf("%d", &y);
  if (y <= 0)
    return list;
  cons *new_head = nullptr, *new_tail = nullptr;
  new_head = read_list(y, &new_tail);
  return append(list, new_head, new_tail);
}

cons* interpret(cons* list) {
  {
    char c;
    while ((c = getchar()) != '\n') {
      if ('A' <= c && c <= 'Z') {
        ungetc(c, stdin);
        break;
      }
    }
  }
  char instruction[2];
  scanf("%[IDA]", instruction);
  cons* result = nullptr;
  switch (instruction[0]) {
  case 'I':
    result = interpret_insert(list);
    break;
  case 'D':
    result = interpret_delete(list);
    break;
  case 'A':
    result = interpret_add(list);
    break;
  default:
    fprintf(stderr, "FATAL! (0x%x) is Not Valid Operation!\n", instruction[0]);
    break;
  }
  return result;
}

int main() {
  int length, ncommand;
  for (int T = 1; T <= 10; T++) {
    scanf("%d", &length);
    cons *list = nullptr;
    list = read_list(length, &global_tail);
    scanf("%d", &ncommand);
    for (int i = 0; i < ncommand; i++)
      list = interpret(list);
    printf("#%d", T);
    dump_list(list, 10);
    printf("\n");
    list->destroy();
    global_tail = nullptr;
  }
}