알고리즘 스터디 스택 1406번
백준 1406번 문제풀이
study안녕하세요. 저는 GDSC 안드로이드 파트 멤버 이하은입니다! 제가 이번 4주차에 맡은 문제는 1406번인데, 어떤 문제인지 같이 보시죠!
https://www.acmicpc.net/problem/1406
문제에서 정의한 에디터 명령어 4가지는 다음과 같습니다.
L은 커서를 왼쪽으로 한칸 이동
D는 커서를 오른쪽으로 한칸 이동
B는 커서의 왼쪽 문자 삭제
P는 커서의 왼쪽에 문자 추가
입력으로 문자열과 에디터 명령어를 받고, 그 명령어를 수행한 결과를 출력하면 됩니다.
std::list 컨테이너 사용하기
먼저 C++ STL에서 제공하는 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.
문제에 주어진 첫번째 예제 입력으로 연습해봅시다!
1. 문자 a,b,c,d를 list에 push
2. P x (커서 왼쪽에 x를 insert)
3. L (커서를 왼쪽으로 한칸 이동)
4. P y (커서 왼쪽에 y를 insert)
C++ 코드
#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을 이용한 풀이
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하면서 출력
커서를 기준으로 왼쪽, 오른쪽 스택을 따로 만든다는 아이디어입니다! 커서는 언제나 두 스택의 사이를 가리키고 있으며, 커서의 이동은 왼쪽, 오른쪽 스택 원소들 간의 삽입, 삭제 연산으로 표현할 수 있습니다.
아까와 마찬가지로, 문제에 주어진 첫번째 예제 입력으로 연습해봅시다!
1. 문자열 abcd 입력 (문자 하나씩 왼쪽 스택에 push)
2. P x (왼쪽 스택에 x를 push)
3. L (커서를 왼쪽으로 이동, 왼쪽 스택의 top을 오른쪽 스택에 push)
4. P y (왼쪽 스택에 y를 push)
최종 결과 (왼쪽 스택의 모든 원소를 오른쪽 스택으로 push 한 뒤에, 오른쪽 스택의 모든 원소를 pop 해주면 LIFO에 따라 다음과 같이 출력됩니다.)
C++ 코드
#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;
}
마지막으로 이 문제를 파이썬으로 풀면 어떻게 되는지 확인해보겠습니다. 파이썬에서는 stack을 리스트로 구현할 수 있습니다. 원소를 추가할 때는 append 함수를, 삭제할 때는 pop 함수를 사용해주면 됩니다.
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))
마무리
커서의 이동을 스택 두 개로 표현할 수 있다는 아이디어가 신박했던 거 같습니다. 문제 유형이 스택이라는 걸 몰랐다면, 그냥 list 컨테이너로 풀고 끝냈을 거 같기도 합니다.
저번 1학기 자료구조 수업 시간에는 stack을 직접 구현했던 거 같은데, C++의 STL에서 제공하는 stack 컨테이너를 사용하면 편하게 문제를 풀 수 있습니다. 그래도 스택이 어떤 자료구조인지는 잘 알고 있어야겠죠! 아래 링크에서 니꼴라스가 설명해주는 스택과 큐 영상을 보면, 쉽게 이해할 수 있을 겁니다!
시험기간이라 다소 급하게 글을 작성한 거 같은데, 그래도 여러분들이 잘 이해하셨을 거라 믿습니다! 2주 뒤에 또 만나요~👋
