[BACKJOON] No.2164 C언어

카드2

자료구조 큐 이용
카드 2와 출력형식이 완전히 같지는 않은데, 비슷한 문제라서 올려본다.

2164번: 카드2

 

Throwing cards

Utilize the Generic implementation of the Queue developed in class(that you can also find in the book) to solve this problem.
In case that your program have memory leaks, points will be deducted for each memory leak.

Given an ordered deck of n cards numbered 1 to n with card 1 at the top and card n at the bottom. The following operation is performed as long as there are at least two cards in the deck:
"Throw away the top card and then move the card that is now on the top to the bottom of the deck."
Your task is to find the sequence of cards thrown away and the last, remaining card in the deck.
Input:
Each line of input (except the last) contains a number n <= 50. The last line contains ‘0’ and this line should not be processed.
Ouput:
For each number from the input produce two lines of output. The first line presents the sequence of discarded cards, the second line reports the last remaining card. No line will have leading or trailing spaces. See the sample for the expected format.
Sample Input:

7

19

10

6

0

Sample Output:

Discarded cards: 1, 3, 5, 7, 4, 2

Remaining card: 6

Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12, 16, 2, 10, 18, 14

Remaining card: 6

Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8

Remaining card: 4

Discarded cards: 1, 3, 5, 2, 6

Remaining card: 4

이해가 잘 안된다면, 괄호가 버린카드임.

Test =7
1 2 3 4 5 6 7

(1)3 4 5 6 7 2 >> (1,3) 5 6 7 2 4 >> (1,3,5) 7 2 4 6 >>
(1,3,5,7)4,6,2 >> (1,3,5,7,4)2,6 >>. 1,3,5,7,4,2

Remaining card = 6


Test = 10
1 2 3 4 5 6 7 8 9 10
>> (1,) 3 4 5 6 7 8 9 10 2 >> (1,3)5 6 7 8 9 10 2 4
>> (1,3,5) 7 8 9 10 2 4 6 >> (1,3,5,7)9 10 2 4 6 8
>> (1,3,5,7,9) 2 4 6 8 10 >> (1,3,5,7,9,2) 6 8 10 4
>> (1,3,5,7,9,2,6)10 4 8 >> (1,3,5,7,9,2,6,10) 8 4
>> (1,3,5,7,9,2,6,10,8) 4

Remaining card = 4





<--코드-->

main.c

#include "queueADT.h" 


int main() { 
  int i=0, e = 0,descheck=1; 
  int arr[20] = { 0, }; 
  
  while (1) { 
    scanf("%d", &arr[i]); 
    if (arr[i] == 0) break; 
    i++; 
  } 
  
  for (int j = 0; j < i; j++) { 
    Queue Que; 
    Queue_init(&Que); 
    
    for (int k = 0; k < arr[j]; k++) {enqueue(&Que, k + 1);}
    
  printf("Discarded cards: "); 
  
  while (!is_empty(&Que)) { 
    e = dequeue(&Que); 
    
    if(descheck<arr[j]) printf("%d", e); 
    if (descheck < arr[j] - 1) printf(", "); 
    
    descheck++; 

    if (is_empty(&Que)) 
      break; 
      e = dequeue(&Que); 
      enqueue(&Que, e); 
    } 
    
    printf("\n"); 
    printf("Remaining card: %d\n", e); 
    descheck = 1; 
  }
  return 0; 
}

queueADT.h

#include <stdio.h> #pragma warning (disable:4996) 
#define SIZE 51 

typedef struct{ 
  int queue[SIZE]; 
  int front,rear; 
}Queue; 

void Queue_init(Queue*q); 
int is_full(Queue*q); 
int is_empty(Queue*q); 
void enqueue(Queue*q, int e); 
int dequeue(Queue*q);

queueADT.c

#include "queueADT.h" 

void Queue_init(Queue*q) { q->front = q->rear = 0; } 
int is_empty(Queue*q) { return (q->front == q->rear); } 
int is_full(Queue*q) { return ((q->rear + 1) % SIZE == q -> front); } 
void enqueue(Queue*q, int e) { 
  if (is_full(q)) return; 
  q->rear = (q ->rear + 1) % SIZE; q->queue[q->rear] = e; 
} 
int dequeue(Queue*q) { 
  if (is_empty(q)) return -1; q->front = (q->front + 1) % SIZE; 
  return q->queue[q->front]; 
}