0x04 - 연결리스트

정의와 성질

연결리스트의 성질

1. K번째 원소를 확인/변경 하깅 위해 O(K)가 필요함

2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 o(1)

3. 원소들이 메모리 상에 연속해있지 않아 히트레이트가 낮지만 할당이 쉬움

   연결 리스트의 종류

   단일 연결 리스트 : 뒤로만 연결
   이중 연결 리스트 : 앞뒤로 연결 (STL)
   원형 연결 리스트 : 끝이 뒤를 가지고 있음

   배열 vs 연결 리스트

   두 자료구조모두 선형 자료구조임

   

1406 에디터

#include <bits/stdc++.h>
using namespace std;

list <char> Edit;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string str;
	cin >> str;
	for (char c : str)
	{
		Edit.push_back(c);
	}
	int n;
	cin >> n;
	auto t = Edit.end();
	for (int i = 0; i < n; i++)
	{
		char command;
		cin >> command;
		if (command == 'L')
		{
			if (t != Edit.begin())
				t--;
		}
		else if (command == 'D')
		{
			if (t != Edit.end())
				t++;
		}
		else if (command == 'B')
		{
			if (t != Edit.begin())
			{
				t--;
				t = Edit.erase(t);
			}
		}
		else
		{
			char c;
			cin >> c;
			Edit.insert(t, c);
			
		}
	}

	for (char c : Edit)
	{
		cout << c;
	}
}

STL list를 활용해볼수있는 문제이다 모두 문제의 조건을 따르되 erase를할때 커서의 앞문자를 지워야하므로 앞으로 간뒤 삭제한다.

5397.키로거

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		list <char> key;
		auto t = key.begin();
		string command;
		cin >> command;
		for (char c : command)
		{
			if (c == '<')
			{
				if (t != key.begin())
					t--;
			}
			else if (c == '>')
			{
				if (t != key.end())
					t++;
			}
			else if (c == '-')
			{
				if (t != key.begin())
				{
					t--;
					t = key.erase(t);
				}
			}
			else
			{
				key.insert(t, c);
			}
		}

		for (char c : key)
		{
			cout << c;
		}
		cout << '\n';

	}
}

위 문제와 동일한 방식으로 풀면 해결할수있다.

1158.요세푸스 문제

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	list <int> yose;

	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++)
	{
		yose.push_back(i);
	}

	cout << '<';
	while (!yose.empty())
	{
		for (int i = 0; i < k -1; i++)
		{
			yose.push_back(yose.front());
			yose.pop_front();
		}
		cout << yose.front();
		yose.pop_front();
		if (yose.empty())
		{
			cout << '>';

		}
		else
		{
			cout << ", ";

		}
	}
}

1부터 n까지의 숫자를 yose리스트에 집어넣고 k-1번동안 리스트의 맨앞의인자를 뒤로 넣어준다.

다음 리스트이 맨앞의 인자를 pop해줌으로써 요세푸스 순열을 구현할수있다 다음 출력형식에 맞게 출력을 해주면 된다.