![#2 코테준비 - 연결리스트](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FRyaiE%2FbtrMIIeWOYe%2FSobZWX4krEBimLCPArFcr0%2Fimg.png)
연결리스트
- 원소를 저장할때 그 다음 원소의 위치를 포함하는 방식으로 저장하는 자료구조
- 원소들은 흩어져 있음
성질
1. k번째 원소를 확인/변경 하기 위해서는 O(k)의 시간복잡도가 필요.(원소들을 타고 가야 하기 때문)
2. 임의의 위치에 원소 추가/제거를 하기위한 시간복잡도는 O(1)임.
3. 연속되어 있지 않아서 Cache Hit rate가 낮지만 할당이 다소 쉬움.
종류
단일 연결리스트
- 다음 원소의 주소 하나만 들고 있는 연결리스트
이중 연결리스트
- 이전,다음원소의 주소를 전부 들고있는 연결리스트
- 주소를 저장할 곳이 하나 더 필요하기 때문에 메모리를 더 씀
- STL의 list가 이중 연결리스트의 구조로 구현이 되어있음
원형 연결리스트
- 끝이 처음와 연결되어있는 연결리스트
연결리스트 문제 풀어보기
백준 1406번 - 에디터 - 1406번: 에디터 (acmicpc.net)
1406번: 에디터
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수
www.acmicpc.net
문자열을 입력받고, 에디터가 주어진 명령어를 몇 번 입력할지에 대한 숫자를 입력받음.
그 숫자동안 반복하면서 명령어를 처리하면 되는 문제다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
list<char> Editor;
string S;
int n = 0;
cin >> S;
for (int i = 0; i < S.length(); i++)
Editor.push_back(S[i]);
list<char>::iterator Cursor = Editor.end();
cin >> n;
while (n--)
{
char a;
cin >> a;
switch (a)
{
case 'L':
{
if(Cursor != Editor.begin())
Cursor--;
}
break;
case 'D':
{
if(Cursor != Editor.end())
Cursor++;
}
break;
case 'B':
{
if(Cursor != Editor.begin())
{
Cursor--;
Cursor = Editor.erase(Cursor);
}
}
break;
case 'P':
{
char temp;
cin >> temp;
Editor.insert(Cursor, temp);
}
break;
}
}
for (auto s : Editor)
{
cout << s;
}
}
명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 하는 조건이 있었기 때문에 iterator를 list의 end로 두고 시작했다.
각 명령어를 case문으로 처리했는데, L,D,P는 주어진 명령어에 맞게 코드를 짜면 끝이였지만, 원소를 지우는 B에서 런타임 에러가 계속 났다.
iterator는 각 원소의 주소를 담고 있지만, 문제에서 요구하는 에디터의 커서는 문자열의 사이사이에 존재한다.
즉, Apple 이라는 단어가 있고 커서는 제일 뒤에 있으며, l을 지워야 한다고 가정한다면
(1) A (2) p (3) p (4) l (5) e (6)
6번에 위치한 커서를 5번으로 옮겨야 지웠을때 l이 지워지는 것이다.( 실제 iterator는 6번일때 e를 가리키고 있기 때문)
커서가 1에 있으면 커서를 더이상 옮길 수 없으니 예외처리를 해주어야 한다.
백준 5397번 - 5397번: 키로거 (acmicpc.net)![](https://blog.kakaocdn.net/dn/c4fMHp/btrMIek9lI3/pcK44SZmNX074v3xbyPjLK/img.png)
5397번: 키로거
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입
www.acmicpc.net
에디터는 명령어를 하나하나 입력하며 푸는 방식이지만, 이 문제는 이미 문자열안에 명령어들이 있고, 그 명령어들을 따라서 암호를 뽑아내면 되는 문제기 때문에 살짝 달랐다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
list<char> KeyLoger = {};
auto p = KeyLoger.begin();
for(auto e:s){
switch (e)
{
case '<':
if (p != KeyLoger.begin())
p--;
break;
case '>':
if (p != KeyLoger.end())
p++;
break;
case '-':
if (p != KeyLoger.begin())
{
p--;
p = KeyLoger.erase(p);
}
break;
default:
{
KeyLoger.insert(p, e);
}
break;
}
}
for (auto e : KeyLoger) cout << e;
cout<<'\n';
}
}
에디터 문제와 비슷했지만 입력받은 문자열을 하나하나 돌면서 명령어를 수행했다.
커서를 옮기고, 문자열을 지우는것은 비슷했으나 명령어가 아닐때 list에 삽입해주는것이 달랐다.
'프로그래밍 공부 > 코딩테스트 준비' 카테고리의 다른 글
#4 코테준비 - 큐(Queue) (0) | 2022.09.23 |
---|---|
#3 코테준비 - 스택(Stack) (0) | 2022.09.22 |
#1 코테 준비 - 배열 (0) | 2022.09.21 |
코테 준비하기 - 기본 사항들 (2) | 2022.09.21 |
LeetCode 문제 풀어보기 - 278번 First Bad Version (0) | 2022.07.22 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!