본문 바로가기
알고리즘/[EXP] 삼성 SW 역량 테스트 C형

BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트

by 피로물든딸기 2023. 8. 25.
반응형

삼성 C형 전체 링크

알고리즘 문제 전체 링크

 

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

 

참고

- BAPC 2010 I번 문제 

- BOJ 5397 : 키로거 (스택)

- 링크드 리스트 Linked List

- 링크드 리스트 삭제

- 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree)

- BOJ 1655 : 가운데를 말해요 with 세그먼트 트리

- 세그먼트 트리를 이용한 링크드 리스트의 삽입과 삭제

- BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트

 

 

위 문제를 스택을 이용한 방법 대신, 세그먼트 트리와 링크드 리스트로 풀어보자.

다만 이 방법으로는 이 문제의 tc를 시간 내에 통과할 수 없다.

 

키로거는 커서를 한 칸씩 이동하면서 움직이기 때문에 스택이나 직접 링크드 리스트로만 구현하는 것이 유리하다.

세그먼트 트리를 이용하는 방식은 임의의 위치에 노드를 삽입하거나 삭제할 때 효과적이다.

 

따라서 input과 output을 참고해서 구현한 내용이 맞는지만 확인해 보자.

(BAPC 2010에서 I번 문제의 input, output을 참고하여 문제를 각색하였다.)

 

아래 input을 참고하자.

input_keylogger.txt
7.54MB

 

코드를 실행해보면, 매우 느리지만 모두 통과하는 것을 알 수 있다.

 

세그먼트 트리(인덱스 트리)를 이용한 링크드 리스트의 삽입과 삭제 구현은 다음과 같다.

#include <stdio.h>
#include <string.h>

#define MAX_LEAF (1048576 * 2) // 2^20

int T;
char input[50][1001000];
char answer[50][1001000];
char myAnswer[1001000];

typedef struct st
{
	char data;
	struct st *next;
}NODE;

NODE HEAD[MAX_LEAF];
NODE POOL[MAX_LEAF];
int pcnt;

int tree[MAX_LEAF * 2];
int leafSize;
int start;
int tIdx = 1;

void showSegment(int size)
{
	for (int i = 1; i <= size; i <<= 1)
	{
		for (int k = i; k <= (i << 1) - 1; k++)
			printf("%d ", tree[k]);
		putchar('\n');

	}

	putchar('\n');
}

void insertNode(NODE* node, int headIndex, int insertIndex)
{
	NODE *curNode = &HEAD[headIndex];

	int curIndex = 1;
	while (1)
	{
		if (insertIndex == curIndex)
		{
			node->next = curNode->next;
			curNode->next = node;

			return;
		}

		curIndex++;
		curNode = curNode->next;
	}
}

void deleteNode(int headIndex, int deleteIndex)
{
	NODE *curNode = &HEAD[headIndex];

	int curIndex = 1;
	while (1)
	{
		if (deleteIndex == curIndex)
		{
			curNode->next = curNode->next->next;
			return;
		}

		curIndex++;
		curNode = curNode->next;
	}
}

void update(int index, int diff)
{
	index += start;

	while (index > 1)
	{
		tree[index] += diff;
		index /= 2;
	}
}

void appendData(char data)
{
	NODE *nd = &POOL[pcnt++];
	nd->data = data;

	update(tIdx, 1);

	nd->next = HEAD[tIdx].next;
	HEAD[tIdx].next = nd;

	tIdx++;
}

void insertData(NODE* nd, int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx << 1]) treeIdx <<= 1;
		else
		{
			index -= tree[treeIdx << 1];
			treeIdx <<= 1;
			treeIdx++;
		}
	}

	insertNode(nd, treeIdx - start, index);
	update(treeIdx - start, 1);
}

void deleteData(int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx << 1]) treeIdx <<= 1;
		else
		{
			index -= tree[treeIdx << 1];
			treeIdx <<= 1;
			treeIdx++;
		}
	}

	deleteNode(treeIdx - start, index);
	update(treeIdx - start, -1);
}

void showData(int tc)
{
	int acnt = 0;
	for (int headIndex = 1; headIndex <= leafSize; headIndex++)
	{
		for (NODE *p = HEAD[headIndex].next; p; p = p->next)
		{
			myAnswer[acnt++] = p->data;
		}
	}

	myAnswer[acnt] = 0;

	if (strcmp(myAnswer, answer[tc]) == 0) printf("tc [%2d] PASS\n", tc);
	else printf("tc [%2d] FAIL\n", tc);
}

int main() 
{
	scanf("%d", &T);

	for (int i = 0; i < T; i++) scanf("%s", answer[i]);
	for (int i = 0; i < T; i++) scanf("%s", input[i]);

	for (int tc = 0; tc < T; tc++)
	{
		char* str = input[tc];	
		int len, keySize, cursor, N, n;

		for (len = 0; str[len]; len++);

		N = len;
		for (n = 1; (1 << n) <= N; n++);
		start = 1 << n;
		start--;

		leafSize = 1 << n;

		for (int i = 1; i <= leafSize * 2; i++) tree[i] = 0;
		for (int i = 1; i <= leafSize; i++) HEAD[i].next = 0;

		pcnt = 0, tIdx = 1;
		keySize = 0, cursor = 1;

		for (int i = 0; i < len; i++)
		{
			char command = str[i];

			if (command == '<')
			{
				if (cursor != 1) cursor--;
			}
			else if (command == '>')
			{
				if (cursor != keySize + 1) cursor++;
			}
			else if (command == '-')
			{
				if (cursor != 1)
				{
					deleteData(cursor - 1);

					cursor--;
					keySize--;
				}
			}
			else
			{
				if (cursor == keySize + 1)
				{
					appendData(command);

					cursor++;
					keySize++;
				}
				else
				{
					NODE* nd = &POOL[pcnt++];
					nd->data = command;

					insertData(nd, cursor);

					keySize++;
					cursor++;
				}
			}
		}

		showData(tc);	
	}

	return 0;
}

 

위의 방법은 전체를 훑은 것이 답이므로 get data는 필요 없었다.

get data로 해당 index의 문자를 알고 싶다면 이 방법을 쓸 수 있다. (물론 더 느리다.)

#include <stdio.h>
#include <string.h>

#define MAX_LEAF (1048576 * 2) // 2^20

int T;
char input[50][1001000];
char answer[50][1001000];
char myAnswer[1001000];

typedef struct st
{
	char data;
	struct st *next;
}NODE;

NODE HEAD[MAX_LEAF];
NODE POOL[MAX_LEAF];
int pcnt;

int tree[MAX_LEAF * 2];
int leafSize;
int start;
int tIdx = 1;

void showSegment(int size)
{
	for (int i = 1; i <= size; i <<= 1)
	{
		for (int k = i; k <= (i << 1) - 1; k++)
			printf("%d ", tree[k]);
		putchar('\n');

	}

	putchar('\n');
}

void insertNode(NODE* node, int headIndex, int insertIndex)
{
	NODE *curNode = &HEAD[headIndex];

	int curIndex = 1;
	while (1)
	{
		if (insertIndex == curIndex)
		{
			node->next = curNode->next;
			curNode->next = node;

			return;
		}

		curIndex++;
		curNode = curNode->next;
	}
}

void deleteNode(int headIndex, int deleteIndex)
{
	NODE *curNode = &HEAD[headIndex];

	int curIndex = 1;
	while (1)
	{
		if (deleteIndex == curIndex)
		{
			curNode->next = curNode->next->next;
			return;
		}

		curIndex++;
		curNode = curNode->next;
	}
}

char getData(int headIndex, int index)
{
	NODE *curNode = &HEAD[headIndex];

	int curIndex = 1;
	curNode = curNode->next;

	while (1)
	{
		if (index == curIndex)
		{
			return curNode->data;
		}

		curIndex++;
		curNode = curNode->next;
	}

	return NULL;
}

void update(int index, int diff)
{
	index += start;

	while (index > 1)
	{
		tree[index] += diff;
		index /= 2;
	}
}

void appendData(char data)
{
	NODE *nd = &POOL[pcnt++];
	nd->data = data;

	update(tIdx, 1);

	nd->next = HEAD[tIdx].next;
	HEAD[tIdx].next = nd;

	tIdx++;
}

void insertData(NODE* nd, int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx << 1]) treeIdx <<= 1;
		else
		{
			index -= tree[treeIdx << 1];
			treeIdx <<= 1;
			treeIdx++;
		}
	}

	insertNode(nd, treeIdx - start, index);
	update(treeIdx - start, 1);
}

void deleteData(int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx << 1]) treeIdx <<= 1;
		else
		{
			index -= tree[treeIdx << 1];
			treeIdx <<= 1;
			treeIdx++;
		}
	}

	deleteNode(treeIdx - start, index);
	update(treeIdx - start, -1);
}

void showData(int tc)
{
	int acnt = 0;
	//for (int headIndex = 1; headIndex <= leafSize; headIndex++)
	//{
	//	for (NODE *p = HEAD[headIndex].next; p; p = p->next)
	//	{
	//		myAnswer[acnt++] = p->data;
	//	}
	//}

	for (int headIndex = 1; headIndex <= leafSize; headIndex++)
	{
		int index = 1;
		for (NODE *p = HEAD[headIndex].next; p; p = p->next)
		{
			myAnswer[acnt++] = getData(headIndex, index);
			index++;
		}
	}

	myAnswer[acnt] = 0;

	if (strcmp(myAnswer, answer[tc]) == 0) printf("tc [%2d] PASS\n", tc);
	else printf("tc [%2d] FAIL\n", tc);
}

int main()
{
	scanf("%d", &T);

	for (int i = 0; i < T; i++) scanf("%s", answer[i]);
	for (int i = 0; i < T; i++) scanf("%s", input[i]);

	for (int tc = 0; tc < T; tc++)
	{
		char* str = input[tc];
		int len, keySize, cursor, N, n;

		for (len = 0; str[len]; len++);

		N = len;
		for (n = 1; (1 << n) <= N; n++);
		start = 1 << n;
		start--;

		leafSize = 1 << n;

		for (int i = 1; i <= leafSize * 2; i++) tree[i] = 0;
		for (int i = 1; i <= leafSize; i++) HEAD[i].next = 0;

		pcnt = 0, tIdx = 1;
		keySize = 0, cursor = 1;

		for (int i = 0; i < len; i++)
		{
			char command = str[i];

			if (command == '<')
			{
				if (cursor != 1) cursor--;
			}
			else if (command == '>')
			{
				if (cursor != keySize + 1) cursor++;
			}
			else if (command == '-')
			{
				if (cursor != 1)
				{
					deleteData(cursor - 1);

					cursor--;
					keySize--;
				}
			}
			else
			{
				if (cursor == keySize + 1)
				{
					appendData(command);

					cursor++;
					keySize++;
				}
				else
				{
					NODE* nd = &POOL[pcnt++];
					nd->data = command;

					insertData(nd, cursor);

					keySize++;
					cursor++;
				}
			}
		}

		showData(tc);
	}

	return 0;
}

 

전체 코드는 다음과 같다.

#include <stdio.h>
#include <string.h>

#define MAX_LEAF (1048576 * 2) // 2^20

int T;
char input[50][1001000];
char answer[50][1001000];
char myAnswer[1001000];

typedef struct st
{
	char data;
	struct st *next;
}NODE;

NODE HEAD[MAX_LEAF];
NODE POOL[MAX_LEAF];
int pcnt;

int tree[MAX_LEAF * 2];
int leafSize;
int start;
int tIdx = 1;

void showSegment(int size)
{
	for (int i = 1; i <= size; i <<= 1)
	{
		for (int k = i; k <= (i << 1) - 1; k++)
			printf("%d ", tree[k]);
		putchar('\n');

	}

	putchar('\n');
}

void insertNode(NODE* node, int headIndex, int insertIndex)
{
	NODE *curNode = &HEAD[headIndex];

	int curIndex = 1;
	while (1)
	{
		if (insertIndex == curIndex)
		{
			node->next = curNode->next;
			curNode->next = node;

			return;
		}

		curIndex++;
		curNode = curNode->next;
	}
}

void deleteNode(int headIndex, int deleteIndex)
{
	NODE *curNode = &HEAD[headIndex];

	int curIndex = 1;
	while (1)
	{
		if (deleteIndex == curIndex)
		{
			curNode->next = curNode->next->next;
			return;
		}

		curIndex++;
		curNode = curNode->next;
	}
}

char getData(int headIndex, int index)
{
	NODE *curNode = &HEAD[headIndex];

	int curIndex = 1;
	curNode = curNode->next;

	while (1)
	{
		if (index == curIndex)
		{
			return curNode->data;
		}

		curIndex++;
		curNode = curNode->next;
	}

	return NULL;
}

char getData(int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx << 1]) treeIdx <<= 1;
		else
		{
			index -= tree[treeIdx << 1];
			treeIdx <<= 1;
			treeIdx++;
		}
	}

	NODE *curNode = &HEAD[treeIdx - start];

	int curIndex = 1;
	curNode = curNode->next;

	while (1)
	{
		if (index == curIndex)
		{
			return curNode->data;
		}

		curIndex++;
		curNode = curNode->next;
	}

	return NULL;
}

void update(int index, int diff)
{
	index += start;

	while (index > 1)
	{
		tree[index] += diff;
		index /= 2;
	}
}

void appendData(char data)
{
	NODE *nd = &POOL[pcnt++];
	nd->data = data;

	update(tIdx, 1);

	nd->next = HEAD[tIdx].next;
	HEAD[tIdx].next = nd;

	tIdx++;
}

void insertData(NODE* nd, int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx << 1]) treeIdx <<= 1;
		else
		{
			index -= tree[treeIdx << 1];
			treeIdx <<= 1;
			treeIdx++;
		}
	}

	insertNode(nd, treeIdx - start, index);
	update(treeIdx - start, 1);
}

void deleteData(int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx << 1]) treeIdx <<= 1;
		else
		{
			index -= tree[treeIdx << 1];
			treeIdx <<= 1;
			treeIdx++;
		}
	}

	deleteNode(treeIdx - start, index);
	update(treeIdx - start, -1);
}

void showData(int tc, int keySize)
{
	int acnt = 0;

	for (int i = 1; i <= keySize; i++) myAnswer[acnt++] = getData(i);

	myAnswer[acnt] = 0;

	if (strcmp(myAnswer, answer[tc]) == 0) printf("tc [%2d] PASS\n", tc);
	else printf("tc [%2d] FAIL\n", tc);
}

int main()
{
	scanf("%d", &T);

	for (int i = 0; i < T; i++) scanf("%s", answer[i]);
	for (int i = 0; i < T; i++) scanf("%s", input[i]);

	for (int tc = 0; tc < T; tc++)
	{
		char* str = input[tc];
		int len, keySize, cursor, N, n;

		for (len = 0; str[len]; len++);

		N = len;
		for (n = 1; (1 << n) <= N; n++);
		start = 1 << n;
		start--;

		leafSize = 1 << n;

		for (int i = 1; i <= leafSize * 2; i++) tree[i] = 0;
		for (int i = 1; i <= leafSize; i++) HEAD[i].next = 0;

		pcnt = 0, tIdx = 1;
		keySize = 0, cursor = 1;

		for (int i = 0; i < len; i++)
		{
			char command = str[i];

			if (command == '<')
			{
				if (cursor != 1) cursor--;
			}
			else if (command == '>')
			{
				if (cursor != keySize + 1) cursor++;
			}
			else if (command == '-')
			{
				if (cursor != 1)
				{
					deleteData(cursor - 1);

					cursor--;
					keySize--;
				}
			}
			else
			{
				if (cursor == keySize + 1)
				{
					appendData(command);

					cursor++;
					keySize++;
				}
				else
				{
					NODE* nd = &POOL[pcnt++];
					nd->data = command;

					insertData(nd, cursor);

					keySize++;
					cursor++;
				}
			}
		}

		showData(tc, keySize);
	}

	return 0;
}
반응형

'알고리즘 > [EXP] 삼성 SW 역량 테스트 C형' 카테고리의 다른 글

BOJ 2338 : 긴자리 계산 with 10^N진법  (0) 2023.08.26
긴자리 후위 표기법 구현하기  (0) 2023.08.25
세그먼트 트리를 이용한 링크드 리스트의 삽입과 삭제  (1) 2023.08.25
2차원 배열 탐색과 캐시 미스 (Cache Misses in 2D Arrays)  (0) 2023.08.15
타입 캐스팅으로 한 번에 메모리 쓰기, 읽기 (Memory Write and Read with Type Casting)  (0) 2023.08.15

관련글

댓글

티스토리툴바