[백준 1406번] 에디터
Updated:
문제 화면
문제 링크 : https://www.acmicpc.net/problem/1406
문제 풀이
이 문제는 stack이나 linked list를 사용해 에디터를 구현하는 문제이다.
stack이나 linked list를 사용할 줄 아는지 물어보는 수준의 문제이기 때문에 stack이나 linked list의 자료구조를 알고 stl stack나 linked list의 문법을 사용할 줄 안다면 어렵지 않은 문제이다. stl 컨테이너들 사용법이 가물가물해서 다시 익힐겸 풀어봤다.
stack의 경우 현재 커서를 기준으로 왼쪽의 문자들과 오른쪽의 문자들을 별도의 stack에 보관하는 방식으로 구현하고 linked list의 경우 insert() 와 erase() 함수를 제공해주기 때문에 하나의 list로 풀 수 있었다.
linked list에서 몇가지 유의할 점은 다음과 같다.
- insert() 와 erase() 함수를 쓸 때 단순 index가 아닌 iterator로 접근해야한다.
- insert()와 달리 erase()를 사용할 경우 iterator를 반환받아서 갱신시켜주어야 한다.
- insert()의 경우 iterator 왼편에 새로운 수 삽입, iterator는 원래 가리키던 수를 가리키고 erase()의 경우 iterator가 가리키던 수 지워버리고, 우측에 있는 수를 가리키게 된다.
제출 코드(stack 사용)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
stack<char> l; // 커서 왼쪽 문자열
stack<char> r; // 커서 오른쪽 문자열
string str;
int num;
char order, letter;
cin >> str;
for (int i = 0; i < str.length(); i++)
{
l.push(str[i]);
}
cin >> num;
for (int i = 0; i < num; i++)
{
cin >> order;
if (order == 'P') // P인 경우 입력 한번 더 받고 l 스택에 넣어주기
{
cin >> letter;
l.push(letter);
}
else if (order == 'L') // 커서가 왼쪽으로 이동 : l 스택의 top을 r로 이동
{
if (!l.empty())
{
r.push(l.top());
l.pop();
}
}
else if (order == 'D') // 커서가 오른쪽으로 이동 : r 스택의 top을 l로 이동
{
if (!r.empty())
{
l.push(r.top());
r.pop();
}
}
else if (order == 'B') // 커서 바로 왼쪽 문자 삭제
{
if (!l.empty())
l.pop();
}
}
while (!l.empty())
{
r.push(l.top());
l.pop();
}
// 출력 위해 한쪽 stack로 몰아넣기
// 시작 문자부터 출력하기 위해 시작 문자가 top이 되도록 l -> r로 이동한다
while (!r.empty())
{
cout << r.top();
r.pop();
} // r 스택의 top 부터 바닥까지 출력
return 0;
}
제출 코드(linked list사용)
#include <iostream>
#include <list>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
list<char> l; // stack 과 달리 하나의 리스트로 해결
string s;
int a;
char first, second;
cin >> s; // string
for(int i = 0 ; i < s.length() ; i++) l.push_back(s[i]);
auto index = l.end(); // auto : 자동으로 형변환해줌 / index가 커서 역할 / 현재 시점에서는 문자열 가장 뒤에 커서가 위치함
cin >> a; // line number
for(int i = 0 ; i < a ; i++) {
cin >> first;
if(first == 'L') { // left 1
if(index!=l.begin()) index--;
}
else if(first == 'D') { // right 1
if(index!=l.end()) index++;
}
else if(first == 'B') { // left delete 1
if(index!=l.begin()) {
index--;
index = l.erase(index); // erase()의 경우 커서 오른쪽 문자 지우게 됨
// cf) insert()의 경우 아무것도 반환하지 않지만 erase()의 경우 iterator를 반환하기 때문에 erase함수를 쓸 경우에는 iterator를 받아서 갱신(저장)하는 방식으로 구현해 주어야 한다
}
}
else if(first == 'P') {
cin >> second;
l.insert(index, second); // 현재 커서 위치에 새로운 문자를 삽입
}
}
for(auto i = l.begin() ; i != l.end() ; i++) {
cout << *i;
} // iterator를 사용해 출력
return 0;
}
결론
이 문제는 stack이나 linked list의 성질을 이용해 문제를 풀 수 있는지를 물어보는 기본적인 문제라고 생각한다. 알고리즘 문제를 풀 때 stack이나 linked list를 잘 아는 것은 중요하기 때문에 자료구조를 잘 이용할 수 있도록 기초를 다지기에 좋은 문제라고 생각한다.
Leave a comment