에디터
📚 문제 설명
문자열과 기능이 주어진다. 각각의 기능은 다음과 같다.
| 명령 | 설명 |
|---|---|
| L | 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) |
| D | 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) |
| B | 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임 |
| P $ | $라는 문자를 커서 왼쪽에 추가함 |
👨🏻💻 풀이 과정
해당 문제를 푸는데 가장 먼저 생각이 난 것은 인접 리스트를 이용하는 것이다.
- 인접 리스트를 이용하여 배열을 저장
- 커서 역할을 하는
this.cur와 마지막 부분을 저장하는this.head를 이용하여 구현 - 각각의 요소는
Node로 구성Node는 현재 값을 나타내는node, 다음 값을 나타내는next, 이전 값을 나타내는prev로 구성
Node 클래스 생성
class Node {
constructor() {
this.node = -1;
this.prev = null;
this.next = null;
}
}List 클래스의 구현은 다음과 같은 느낌이다.
this.head는 배열의 끝부분을 의미한다.- 처음 선언시
this.cursor는 배열의 끝부분으로 초기화 되어 있다. Push함수는 커서 왼쪽에 값을 추가한다.this.cursor왼쪽 연결만 변경하면 된다는 뜻
- 커서 위치 변경시 연결 부분으로 커서를 변경
- 그럼 이제
this.cursor는 끝부분인this.head가 아니다.
- 그럼 이제
- 마지막에는
this.cursor의 위치를 맨 끝부분인this.head로 바꾸어서 계산
인접 노드 생성 및 기능 구현
class LIST {
constructor() {
// 끝부분을 의미
this.head = new Node();
// 커서를 의미
this.cursor = this.head;
}
MoveLeft() {
if (this.cursor.prev) {
this.cursor = this.cursor.prev;
}
}
MoveRight() {
if (this.cursor.next) {
this.cursor = this.cursor.next;
}
}
Delete() {
// 커서의 이전 부분
const DeleteItem = this.cursor.prev;
// 커서가 왼쪽 끝일 때를 의미
if (DeleteItem == null) {
return;
}
// 커서 이전의 이전을 의미
// 예를 들어 [1,2,커서] 라면 1을 의미
// DeleteItem.prev 값과 연결된 부분을 수정
if (DeleteItem.prev !== null) {
DeleteItem.prev.next = DeleteItem.next;
}
// 결국 this.cursor.prev 값을 의미
if (DeleteItem.next !== null) {
DeleteItem.next.prev = DeleteItem.prev;
}
}
Push(item) {
//새로 추가할 Node 생성
let newItem = new Node();
newItem.node = item;
newItem.prev = this.cursor.prev;
newItem.next = this.cursor
;
// 만약 커서 이전 값이 존재하면
if (this.cursor.prev) {
// 커서 이전 값의 다음을 새로운 Node로
this.cursor.prev.next = newItem;
}
// 커서의 이전 부분을 새로운 Node로
this.cursor.prev = newItem;
}
getNode() {
if (this.cursor.node) {
return this.cursor.node;
}
}
SetBegin() {
this.cursor = this.head;
}
isEnd() {
return !this.cursor.prev;
}
}메인 로직에서 중요하게 생각한 부분은
- 명령 시행 후 커서의 위치는 마지막 명령 지점
- 따라서 커서 위치를
SetBegin을 이용하여 가장 끝 부분으로 옮겨줌
- 따라서 커서 위치를
- 그 후
isEnd를 이용하여 커서가 시작 지점까지 왔는지 확인하며 반복문 순회- 반복문을 돌며 커서 위치 왼쪽으로 이동, 값을
answer배열에 삽입
- 반복문을 돌며 커서 위치 왼쪽으로 이동, 값을
- 마지막부터 왔기 때문에 출력하기 전에
reverse()를 이용해 배열을 뒤집음
메인 로직 부분
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
//처음 배열
let arr = input.shift().split('');
// 명령 갯수
let n = input.shift();
// 명령
input = input.map(v => v.split(' '));
let answer = [];
class Node{ //생략 }
class LIST{ //생략 }
const list = new LIST();
// 처음 배열 삽입
for (let i = 0; i < arr.length; i++) {
list.Push(arr[i]);
}
// 명령 수행
for (let i = 0; i < input.length; i++) {
const [Order, item = '0'] = input[i];
switch (Order) {
case 'P':
list.Push(item);
break;
case 'L':
list.MoveLeft();
break;
case 'D':
list.MoveRight();
break;
case 'B':
list.Delete();
break;
default:
break;
}
}
// 커서의 위치가 마지막 위치이기 때문에 끝으로 이동
list.SetBegin();
// 커서가 배열 시작 부분까지 오면 종료
while (!list.isEnd()) {
list.MoveLeft();
answer.push(list.getNode());
}
// 커서가 끝에서 시작점으로 이동하며 값을 push 하기 때문에 reverse() 해야함
console.log(answer.reverse().join(''));전체 풀이
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
//처음 배열
let arr = input.shift().split('');
// 명령 갯수
let n = input.shift();
// 명령
input = input.map(v => v.split(' '));
let answer = [];
class Node {
constructor() {
this.node = -1;
this.prev = null;
this.next = null;
}
}
class LIST {
constructor() {
// 끝부분을 의미
this.head = new Node();
// 커서를 의미
this.cursor = this.head;
}
MoveLeft() {
if (this.cursor.prev) {
this.cursor = this.cursor.prev;
}
}
MoveRight() {
if (this.cursor.next) {
this.cursor = this.cursor.next;
}
}
Delete() {
// 커서의 이전 부분
const DeleteItem = this.cursor.prev;
// 커서가 왼쪽 끝일 때를 의미
if (DeleteItem == null) {
return;
}
// 커서 이전의 이전을 의미
// 예를 들어 [1,2,커서] 라면 1을 의미
// DeleteItem.prev 값과 연결된 부분을 수정
if (DeleteItem.prev !== null) {
DeleteItem.prev.next = DeleteItem.next;
}
// 결국 this.cursor.prev 값을 의미
if (DeleteItem.next !== null) {
DeleteItem.next.prev = DeleteItem.prev;
}
}
Push(item) {
//새로 추가할 Node 생성
let newItem = new Node();
newItem.node = item;
newItem.prev = this.cursor.prev;
newItem.next = this.cursor
;
// 만약 커서 이전 값이 존재하면
if (this.cursor.prev) {
// 커서 이전 값의 다음을 새로운 Node로
this.cursor.prev.next = newItem;
}
// 커서의 이전 부분을 새로운 Node로
this.cursor.prev = newItem;
}
getNode() {
if (this.cursor.node) {
return this.cursor.node;
}
}
SetBegin() {
this.cursor = this.head;
}
isEnd() {
return !this.cursor.prev;
}
}
//LIST 생성
const list = new LIST();
// 처음 배열 삽입
for (let i = 0; i < arr.length; i++) {
list.Push(arr[i]);
}
// 명령 수행
for (let i = 0; i < input.length; i++) {
const [Order, item = '0'] = input[i];
switch (Order) {
case 'P':
list.Push(item);
break;
case 'L':
list.MoveLeft();
break;
case 'D':
list.MoveRight();
break;
case 'B':
list.Delete();
break;
default:
break;
}
}
// 커서의 위치가 마지막 위치이기 때문에 끝으로 이동
list.SetBegin();
// 커서가 배열 시작 부분까지 오면 종료
while (!list.isEnd()) {
list.MoveLeft();
answer.push(list.getNode());
}
// 커서가 끝에서 시작점으로 이동하며 값을 push 하기 때문에 reverse() 해야함
console.log(answer.reverse().join(''));
해당 풀이를 진행한 후 다른 사람들의 풀이를 봤는데 정말 깜짝 놀랐다.
그 방식은 2개의 스택을 이용하는 풀이였다.
💡스택 이용 풀이
스택을 이용한 풀이의 기본은 커서를 기준으로 두개의 스택이 나누어져 있다고 보는 생각에서 나오는 것 같다.
Stack // cursor // Stack
이런식으로 생각을 하고 푸는 것이다. 그럼 해당 기능에 대한 생각도 다음과 같이 바뀌게 된다.
| 명령 | 원래 생각 | 2개의 스택일 때 |
|---|---|---|
| L | 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) | 왼쪽 스택에서 pop() 한 후 오른쪽에 push() |
| D | 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) | 오른쪽 스택에서 pop() 한 후 왼쪽으로 push() |
| B | 커서 왼쪽에 있는 문자를 삭제함 | 왼쪽 스택에서 pop() |
| P $ | $라는 문자를 커서 왼쪽에 추가함 | 왼쪽 스택에 push() |
전체 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let leftArray = input.shift().split('');
let rightArray = [];
let n = input.shift();
// 명령 수행
for (const OrderList of input) {
const [Order, Element= null] = OrderList.split(' ');
switch (Order) {
case 'P':
leftArray.push(Element);
break;
case 'L':
if (leftArray.length) {
rightArray.push(leftArray.pop());
}
break;
case 'D':
if (rightArray.length) {
leftArray.push(rightArray.pop());
}
break;
case 'B':
leftArray.pop();
break;
default:
break;
}
}
// 오른쪽 스택은 거꾸로 되어 있기 때문에 reverse() 진행
console.log(leftArray.concat(rightArray.reverse()).join(''));🧐 후기
최근들어 JavaScript로 구현을 직접하는 문제들을 많이 풀어서 그런지 해당 문제도 당연히 그런 방향으로 생각을 했던 것 같다.
힘들게 인접 리스트를 구현 했다가 2개의 스택을 이용하여 쉽게 푸는 풀이를 보고 정말 놀랐고 내가 왜 이런 생각을 못했을까 하고 안타까웠다.
분명 이렇게 인접 리스트를 사용하여 구현을 하는 방식 또한 다음에 언젠가 도움이 되겠지만 앞으로는 문제에 대한 접근을 조금 더 생각해 봐야겠다는 생각을 했다.
JavaScript를 사용하는 모두를 위해...