백준 2002 추월

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

2002번: 추월

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef enum { false, true } bool;
int cnt = 0;
typedef struct _Node
{
	char carNum[9];
	struct _Node* next;
}Node;

typedef struct
{
	Node* head;
	int len;
	Node* tail;
}LinkedList;

bool IsEmpty(LinkedList* plist)
{
	return plist->len == 0;
}
void InitList(LinkedList* plist)
{
	plist->len = 0;
	plist->head = (Node*)malloc(sizeof(Node));
	plist->tail = (Node*)malloc(sizeof(Node));
	plist->head = plist->tail;
}
void Insert(LinkedList* plist, char* item)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	strcpy(newNode->carNum, item);

	if (IsEmpty(plist))
	{
		plist->tail = newNode;
		plist->head = newNode;
	}
	else
	{
		plist->tail->next = newNode;
		plist->tail = newNode;
	}
	(plist->len)++;
}
bool Compare(LinkedList* Inlist, LinkedList* OutList)
{
	Node* Incur, * OutCur;
	Incur = Inlist->head;
	OutCur = OutList->head;
	while (Incur != Inlist->tail && OutCur != Inlist->tail)
	{
		if (strcmp(Incur->carNum, OutCur->carNum) != 0)
			return false;
		Incur = Incur->next;
		OutCur = OutCur->next;
	}
	return true;
}
void RemoveMiddle(LinkedList* plist, char* item)
{
	Node* cur, * temp, * before;
	if (strcmp(item, plist->head->carNum)==0)
	{
		temp = plist->head;
		plist->head = plist->head->next;
		(plist->len)--;
		free(temp);
		return;
	}
	cur = plist->head;
	before = plist->head;
	while (strcmp(cur->carNum, item) != 0)
	{
		before = cur;
		cur = cur->next;
	}
	temp = cur;
	if (cur == plist->tail)
		before = plist->tail;
	else
		before->next = cur->next;
	(plist->len)--;
	free(temp);
}
void PrintCarCnt(LinkedList* Inlist, LinkedList* Outlist)
{
	
	while (!Compare(Inlist, Outlist)) //Inlist와 Outlist가 같아질 때까지 반복한다.
	{
		Node* Incur = Inlist->head;
		Node* Outcur = Outlist->head;
		while (strcmp(Incur->carNum, Outcur->carNum) == 0)
		{
			Outcur = Outcur->next;
			Incur = Incur->next;
		}
		RemoveMiddle(Inlist, Outcur->carNum);
		RemoveMiddle(Outlist, Outcur->carNum);
		cnt++;
	}
	printf("%d", cnt);
}

int main()
{
	LinkedList InputList;
	LinkedList OutputList;
	InitList(&InputList);
	InitList(&OutputList);

	int N;
	scanf("%d", &N);
	char IncarNum[9];
	char OutcarNum[9];
	for (int i = 0; i < N; i++)
	{
		scanf("%s", IncarNum);
		Insert(&InputList, IncarNum);
	}
	for (int i = 0; i < N; i++)
	{
		scanf("%s", OutcarNum);
		Insert(&OutputList, OutcarNum);
	}
	PrintCarCnt(&InputList, &OutputList);

	return 0;
}

대근이의 차량번호 목록을 InputList로, 영준이의 차량번호 목록을 OutputList로 연결리스트를 만든다.

영준이의 헤드와 대근이의 헤드가 다를 경우 영준이의 헤드에 해당하는 차번호를 대근이의 리스트에서 삭제한다. 

동시의 영준이의 차번호도 삭제한다. 삭제할 때마다 count를 증가시킨다. 

두 리스트가 같아질 때까지 반복한다.