07.04. 행운의 바퀴 [Linked List][백준 2840]

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

2840번: 행운의 바퀴

 

Algorithm classification : Linked List, Simulation

 

07.04.1. Problem

Mirko has recently bought a wheel of fortune. He wrote an uppercase letter of English alphabet onto each wedge, like this:

No letter appears twice in the wheel, and the wheel spins in clockwise direction. There is a pointer that stays in the same place while the wheel is spinning (it is pointing to H in the picture above). When we spin the wheel, the letter to which the pointer is pointing to changes accordingly.

 

Mirko spinned the wheel K times in a row, and each time he wrote down how many times the pointed letter changed, and what letter was pointed to at the end of that spin.

 

Slavko found that paper, and would like to now what letters Mirko wrote onto the wedges of the wheel. Help him determine this, if the total number of wedges is known.

 

 

07.04.2. Input limit

The first line of input contains integers N (2 ≤ N ≤ 25), the number of wedges on the wheel, and K (1 ≤ K ≤ 100), the number of spins.

 

The following K lines contain descriptions Mirko wrote down for each spin, in order. Each line contains an integer S (1 ≤ S ≤ 100), the number of times the pointed letter changed during that spin, and an uppercase letter at which pointer stopped.

 

 

07.04.3. Output

If there is no wheel that meets the requirements described, output ‘!’.

 

Otherwise, output sequence of letters written onto the wheel, starting from the pointed letter at the end of the last spin and proceeding clockwise. If some letter can’t be determined, output ‘?’ instead.

 

07.04.4. Solution

이제 기본적인 node나 list 구성은 익숙해지셨다고 생각합니다.

typedef struct node{
	int index;
	char data;
	struct node* next;
	struct node* prev;
}NODE;

typedef struct list{
	NODE* head;
	int size;
}LIST;

void insert(LIST* l);
int check(LIST* l, int t, char a);

같은 문자가 나오지 않는다는 것을 고려하셔야 합니다.

int main()
{
	int n, i, k, t;
	char a;
	
	scanf("%d %d", &n, &k);
	LIST* l = (LIST*)malloc(sizeof(LIST));
	l->head = NULL;
	l->size = 0;
	for(i = 0; i < n; i++){
		insert(l);
	}
	
	for(i = 0; i < k; i++){
		scanf("%d %c", &t, &a);
		if(!check(l, t, a)){
			printf("!");
			return 0;
		}
	}
	int count[30] = {0};
	
	for(i = 0; i < n; i++){
		if(l->head->data){
			count[l->head->data - 'A']++;
			if(count[l->head->data - 'A'] > 1){	
				printf("!");
				return 0;	
			}
		}
		l->head = l->head->next;
		
	}
	for(i = 0; i < n; i++){
		printf("%c", l->head->data ? l->head->data : '?');
		l->head = l->head->prev;
	}
	NODE* removeNode;
	while(l->size){
		removeNode = l->head;
		l->head = l->head->next;
		l->size--;
	}
	free(l);
	
	return 0;
}

 

node insert function code는 이제 재활용하는군요.

void insert(LIST* l){
	NODE* newNode = (NODE*)malloc(sizeof(NODE));
	newNode->data = NULL;
	newNode->next = newNode->prev = newNode;
	newNode->index = l->size + 1;
	
	if(l->head == NULL){
		l->head = newNode;
	}
	else{
		NODE* curNode = l->head;
		for(int i = 1; i < l->size; i++){
			curNode = curNode->next;
		}
		curNode->next = newNode;
		newNode->prev = curNode;
		l->head->prev = newNode;
		newNode->next = l->head;
	}
	l->size++;
}

int check(LIST* l, int t, char a){
	for(int i = 0; i < t; i++){
		l->head = l->head->next;
	}
	if(l->head->data == NULL){
		l->head->data = a;	
		return 1;
	}
	else if(l->head->data != a){
		return 0;
	}
	return 1;
}

 

 

몇개의 test case를 도움되시라고 적어두겠습니다.

4 3
1 A
1 B
3 A
>> A??B

 

2 3
1 A
1 B
1 C
>> !

2 3
1 A
1 A
1 B
>> !


5 4
1 A
2 B
1 C
2 A
>> A?CB?

 

4 4
1 A
1 A
1 A
1 A
>> !