https://www.acmicpc.net/problem/1406
문제분석
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
L
|
커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
|
D
|
커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
|
B
|
커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
|
P $
|
$라는 문자를 커서 왼쪽에 추가함
|
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
문제풀이
해당 문제는 리스트(자세히 말하자면 더블 링크드 리스트) 또는 스택을 이용해 해결 가능한 문제이다.
이번 포스팅에서는 리스트를 이용해 풀어보겠다!
시간제한이 있는 문제이므로 혹시 모르니 입출력 속도를 높여주고,
1. 리스트를 하나 선언하여 string의 값을 리스트에 넣어준다.
-> 이 코드는 list<char> li(s.begin(),s.end()); 와 같이 표현가능하다!
2. 반복자를 하나 생성하여 해당 리스트의 맨 뒤를 가리키게 한다.
-> 굳이 iterator선언 없이 auto 키워드를 이용해 생성가능하다.
-> 참고로 end()는 리스트의 맨 마지막을 가리키는 것이 아니라, 맨 마지막의 다음을 가리키고 있다고 한다!
3. P 명령일 땐, 단어 하나를 더 입력받아 현재 커서(=iter)가 end()일 경우 맨 뒤에 위치하고 있음을 뜻하므로 push_back해준다.
그렇지 않으면 해당 커서의 위치에 추가한다.
(리스트는 해당 iter가 가리키는 위치에 추가하면, 그 위치 뒤에 오는 모든 요소를 뒤로 밀어버리고 생기는 빈 공간에 요소를 추가한다. = 왼쪽에 추가!)
※ 리스트에 {'A', 'B', 'C'}가 있다고 하자 (편의상 대충 표기함)
현재 iter가 B를 가리키고 있다고 할 때, li.insert(iter, 'ㅋ'); 을 실행하면
{'A', 'ㅋ', 'B', 'C'} 이렇게 iterator의 왼쪽에 요소를 추가하고 여전히 iterator는 'B'를 가리킨다!
4. L 명령일 땐, 리스트의 begin()이 아니라면 iter를 감소시킨다.
5. D 명령일 땐, 리스트의 end()가 아니라면 iter를 증가시킨다.
6. B 명령일 땐,
- 커서가 현재 맨 오른쪽이면 pop_back해준다.
- 맨 앞이면 무시한다.
- 맨 앞, 뒤가 아니라면, iter를 감소시키고 erase 해준다.
※ erase는 삭제를 수행한 이후에 iterator를 반환한다. 따라서 반드시 반환되는 반복자를 받아서 저장하는 방식으로 구현해야한다!
※ 리스트에 {'A', 'B', 'C'}가 있다고 하자
iter는 현재 'B'를 가리키고 있는 상태에서 iter = li.erase(iter)를 실행하게 되면, {'A', 'C'}와 같은 상태가 되고, iterator는 B 뒤에 있던 C를 가리키게 된다.
따라서 커서 왼쪽의 값을 삭제하고 원래 가리키던 걸 가리키게 하려면 먼저 반복자를 하나 감소시킨 뒤, 삭제를 진행해야한다!
#include<iostream>
#include<algorithm>
#include<list>
#include<string>
using namespace std;
list<char> li;
list<char>::iterator iter ; //반복자 선언
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s;
char instruction, ch;
int n;
cin >> s >> n;
for (int i = 0; i < s.length(); i++) {
li.push_back(s[i]);
}
iter = li.end();
while (n--) {
cin >> instruction;
if (instruction == 'P') {
cin >> ch;
if (iter == li.end()) { // 맨 뒤면 맨 뒤에 삽입
li.push_back(ch);
iter = li.end();
}
else { // 아니면 중간에 삽입
li.insert(iter, ch);
//iter++;
}
}
else if (instruction == 'L') { // 맨 앞 아니면 커서 왼쪽으로 이동시킴
if (iter != li.begin()) {
iter--;
}
}
else if (instruction == 'D') { // 맨 뒤 아니면 커서 오른쪽으로 이동시킴
if (iter != li.end()) {
iter++;
}
}
else if (instruction == 'B') {
if (iter == li.end()) { // 커서가 맨 오른쪽이면 맨 뒤 삭제
li.pop_back();
// iter = li.end();
}
else if (iter == li.begin()) { // 커서가 맨 앞이면 무시
continue;
}
else { // 맨 앞, 맨 뒤 모두 아니면 커서 왼쪽의 문자 삭제
iter--;
iter = li.erase(iter);
}
}
}
for (iter = li.begin(); iter != li.end(); iter++) {
cout << *iter;
}
return 0;
}
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/C++] 1987번 알파벳 (0) | 2022.09.29 |
---|---|
[백준/C++] 19948번 음유시인 영재 (0) | 2022.09.29 |
[백준/C++] 14465번 소가 길을 건너간 이유 5 (0) | 2022.09.28 |
[백준/C++] 2668번 숫자고르기 (0) | 2022.09.27 |
[백준/C++] 1916번 최소비용 구하기 (0) | 2022.09.26 |