GDSC 팀블로그에도 포스팅한 문제입니다!
https://gdsc-seoultech.github.io/posts/2021-10-14-python_1406/
https://www.acmicpc.net/problem/1406
문제를 요약하면 다음과 같다.
L은 커서를 왼쪽으로 이동
D는 커서를 오른쪽으로 이동
B는 커서 왼쪽에 있는 문자 삭제
P는 커서 왼쪽에 문자 추가
연결 리스트를 이용한 풀이
1. 알고리즘 이해
먼저 list 컨테이너 기본 사용법부터 알아야 한다.
https://blockdmask.tistory.com/76
특히, end()와 insert()는 주의할 점이 있다. end는 마지막 원소 바로 다음 위치를 가리키며, insert는 지정한 위치 바로 앞부분에 원소를 삽입한다!
https://www.cplusplus.com/reference/list/list/insert/
The container is extended by inserting new elements before the element at the specified position.
문제에 주어진 첫번째 예제 입력으로 연습해보자!
-
문자열 abcd 입력 후, 연결 리스트 초기화
-
P x (커서 왼쪽에 x를 insert)
-
L (커서를 왼쪽으로 한칸 이동)
-
P y (커서 왼쪽에 y를 insert)
2. 코드로 구현
#include <iostream>
#include <string>
#include <list>
using namespace std;
int main() {
string s;
cin >> s;
// 문자 하나씩 연결리스트에 추가
list<char> l(s.begin(), s.end());
//list<char>::iterator now = l.end();
auto cur = l.end();
// end()는 마지막 원소 바로 다음 위치를 가리킴.
int n;
cin >> n;
while (n--) {
char cmd;
cin >> cmd;
if (cmd == 'L') {
if (cur != l.begin()) {
cur--; // 왼쪽 이동
}
}
else if (cmd == 'D') {
if (cur != l.end()) {
cur++; // 오른쪽 이동
}
}
else if (cmd == 'B') {
if (cur != l.begin()) {
cur = l.erase(--cur);
// 커서의 왼쪽 원소 삭제
}
}
else if (cmd == 'P') {
char c;
cin >> c;
l.insert(cur, c);
// 커서의 바로 앞부분에 삽입
}
}
/*for (auto it = l.begin(); it != l.end(); it++) {
cout << *it;
}*/
for (auto& e : l) { // 범위 기반 for문
cout << e;
}
return 0;
}신박한 풀이: stack 이용
1. 핵심 아이디어
https://intaehwang.tistory.com/32
- 커서를 기준으로 왼쪽 stack, 오른쪽 stack을 선언한다.
- L일 경우, 왼쪽 stack top을 오른쪽 stack으로 push
- D일 경우, 오른쪽 stack top을 왼쪽 stack으로 push
- B일 경우, 왼쪽 stack top을 pop
- P일 경우 왼쪽 stack에 push
- 출력할 땐, 왼쪽 stack 전체를 오른쪽으로 push
- 오른쪽 stack 전체를 pop하면서 출력
커서를 기준으로 왼쪽, 오른쪽 스택을 따로 생성한다는 아이디어! 커서는 언제나 두 스택의 사이를 가리키고 있으며, 커서의 이동은 왼쪽, 오른쪽 스택 원소 간의 삽입, 삭제 연산으로 표현할 수 있다.
아까와 마찬가지로, 문제에 주어진 첫번째 예제 입력으로 연습해보자!
-
문자열 abcd 입력 (문자 하나씩 왼쪽 스택에 push)
-
P x (왼쪽 스택에 x를 push)
-
L (커서를 왼쪽으로 이동, 왼쪽 스택의 top을 오른쪽 스택에 push)
-
P y (왼쪽 스택에 y를 push)
최종 결과
2. 코드로 구현
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
stack<char> l;
stack<char> r;
// 왼쪽 스택에 입력된 모든 문자를 push
for (int i = 0; i < s.size(); i++) {
l.push(s[i]);
}
int num;
cin >> num;
while (num--) { // num == 0이면 종료
char cmd;
cin >> cmd;
// P: 왼쪽 스택의 top에 추가
if (cmd == 'P') {
char c;
cin >> c;
l.push(c);
}
// B: 왼쪽 스택이 비어있지 않다면, 왼쪽의 top 삭제
else if (cmd == 'B') {
if (l.empty()) continue;
else l.pop();
}
// L: 왼쪽 스택이 비어있지 않다면, 왼쪽의 top을 오른쪽에 push
else if (cmd == 'L') {
if (l.empty()) continue;
else {
r.push(l.top());
l.pop();
}
}
// D: 오른쪽 스택에 비어있지 않다면, 오른쪽의 top을 왼쪽에 push
else if (cmd == 'D') {
if (r.empty()) continue;
else {
l.push(r.top());
r.pop();
}
}
}
// 왼쪽 스택 전체를 오른쪽 스택에 push
while (!l.empty()) {
r.push(l.top());
l.pop(); // LIFO
}
// 오른쪽 스택 전체 출력 (LIFO)
while (!r.empty()) {
cout << r.top();
r.pop(); // LIFO
}
return 0;
}Python 풀이
from sys import stdin
left = list(stdin.readline().strip())
right = []
n = int(input())
for _ in range(n):
temp = stdin.readline()
if temp[0] == 'L':
if len(left) == 0:
continue
right.append(left.pop())
elif temp[0] == 'D':
if len(right) == 0:
continue
left.append(right.pop())
elif temp[0] == 'B':
if len(left) == 0:
continue
left.pop()
elif temp[0] == 'P':
left.append(temp[2])
# 오른쪽 리스트 원소들의 순서를 뒤집어서 왼쪽 리스트에 붙이고 전체 출력
#right.reverse()
#left.extend(right)
left.extend(right[::-1])
print("".join(left))