Linked list with Stack Node 문제

Q2.c

0.00MB

 

이번 문제는 Linked list를 C 코드로 구현하는 것인데, 특이점은 각 Node가 Stack 구조라는 것이다.

즉 아래와 같이 Linked list Node가 존재한다는 것!

 

 

다시 말하면, 밖에서 봤을 땐 하나의 커다란 Stack인데 이것들이 내부에선 Linked list로 구성이 되어 있다는 것이다.

문제의 조건은 아래와 같다.

 

  1. 각 Stack Node에는 Max-capacity가 존재하다. Max-capacity를 넘어서면 새로운 Stack Node를 만든다.

 

  2. list_size() method를 구현하라. 현재 원소가 존재하는 List Node(stack)의 개수를 반환한다.

 

  3. push() method를 구현하라.

 

  4. pop() method를 구현하라. 원소가 Linked list에 없을 땐 -9999를 반환한다.

 

Skeleton Code와 test case는 위에 첨부되어 있으니 참고해서 문제를 풀어봅시다.

 

---

 

일단 풀긴 풀었는데, 좀 짜치는 부분이 있다.

 

Skeleton Code 외에 다른 것은 못 건든다고 가정하고 코드풀이를 진행할 시,

 

처음에 ListNode의 Stack에 대한 초기화가 되어있지 않아서 낭패였다.

 

그래서 낚인게, ListNode initialize를 해줄 때, *Stack에 대해서도 malloc 할당을 해주지 않아 계속 segmantaion fault가 떴다.. 이거 때문에 개고생함..

 

그래서 유야무야 만들어낸 코드는 아래와 같다.

 

위 이슈를 해결하기위해 온갖 노력을 해봤지만 결국 GPT언니에게 좀 물어봤다 ㅠㅠ

 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Stack {
  int size;
  int* arr;
} Stack;

typedef struct ListNode { // 기본 제공
  struct ListNode *next;
  struct Stack *stack;
  int stack_capacity;
} ListNode;

int list_size(ListNode *head) {
  // printf("size check!!!\n");
  int ans = 0;
  if(head->stack->size > head->stack_capacity || head->stack->size == 0) return ans;
  // 처음 size를 어떻게 0을 반환하냐 진짜.. 초기화가 없는데

  ListNode* temp = head;
  while(temp){
    ans++;
    temp = temp->next;
  }
  return ans;
}

void push_los(ListNode *head, int val) {
  // head가 없는 경우( 여기서도 초기화 이슈로 인한 이상한 조건문 추가-_- )
  if(!head->next && head->stack->size > head->stack_capacity){
    head->stack = (Stack*)malloc(sizeof(Stack));
    head->stack->arr = (int*)malloc(sizeof(int)*(head->stack_capacity));
    head->stack->size = 0;
    head->stack->arr[head->stack->size++] = val;
    // printf("1part debug : %d\n",val);
    return;
  }
  // head가 있다 -> 마지막 Node를 찾아라
  ListNode* temp = head;
  while(temp->next){
    temp = temp->next;
  }
  //Stack Node가 꽉 안 찼다.
  if(temp->stack->size < head->stack_capacity){
    temp->stack->arr[head->stack->size++] = val;
    // printf("2part debug : %d\n",val);
    return;
  }
  //Stack Node가 꽉 차서 다음 Node로 넘어가야 한다.
  if(temp->stack->size == head->stack_capacity){
    ListNode *new_node = (ListNode *) malloc(sizeof(ListNode));
    new_node->next = NULL;
    new_node->stack_capacity = 3;
    new_node->stack = (Stack*)malloc(sizeof(Stack)); // 아 이것도 해줘야하는 거였다..
    temp->next = new_node;

    new_node->stack->arr = (int*)malloc(sizeof(int)*(head->stack_capacity));
    new_node->stack->size = 0;
    new_node->stack->arr[new_node->stack->size++] = val;
    // printf("3part debug : %d\n",val);
  }
  
}

int pop_los(ListNode *head) {
  // 여기서도 초기화 이슈로 인한 이상한 조건문 추가-_-
  if(head->stack->size == 0 || head->stack->size > head->stack_capacity ) return -9999;
  if(!head->next){
    int ans = head->stack->arr[--(head->stack->size)];
    return ans;
  }
  ListNode* prev = NULL;
  ListNode* curr = head;
  while(curr->next){
    prev = curr;
    curr = curr->next;
  }
  int ans = curr->stack->arr[--(curr->stack->size)];
  if(curr->stack->size == 0){
    prev -> next = NULL;
    free(curr);
  }
  return ans;
}

int main(){
  ListNode *head = (ListNode *) malloc(sizeof(ListNode));
  head->next = NULL;
  head->stack_capacity = 3;
  printf("%d,ans:-9999\n", pop_los(head)); // -9999

  printf("%d,ans:0\n", list_size(head)); // 0 

  push_los(head, 10);
  push_los(head, 5);
  push_los(head, 4);
  printf("%d,ans:1\n", list_size(head)); // 1

  push_los(head, 18);
  printf("%d,ans:2\n", list_size(head)); // 2

  printf("%d,ans:18\n", pop_los(head)); // 18 
  printf("%d,ans:4\n", pop_los(head)); // 4

  printf("%d,ans:1\n", list_size(head)); // 1

  printf("%d,ans:5\n", pop_los(head));  // 5
  printf("%d,ans:10\n", pop_los(head)); // 10
  printf("%d,ans:-9999\n", pop_los(head)); // -9999

  printf("%d,ans:0\n", list_size(head)); // 0
}

 

어찌어찌 문제를 풀었으니,

 

내가 햇갈렸던 부분에 대해서도 GPT 도움을 좀 받아보기로 한다.

 

찾아보니 뭔가 문제에 오류가 있던 거 같다.

 

아무래도 완벽한 문제 복기본이 아니라 그런가보다.

 

main함수를 고칠 수 없다는 가정하에 Node의 Stack 초기화 없이 안정적으로 Linked List Stack을 구현하는 것은 불안정요소가 있을 수밖에 없다는 것이 나의 합리화..

 

일단 오늘은 여기까지...!