AC
📚 문제 설명
- R과 D 두가지 연산이 있다.
- R은 배열 뒤집기
- D는 첫번째 값 꺼내기
- 입력은 첫줄은 테스트 횟수, 그 다음줄부터는 명령, 배열 크기, 배열 순이다.
입력
4 - 테스트 횟수
RDD - 명령어
4 - 배열 수
[1,2,3,4] - 배열
DD - (명령어, 배열 수, 배열) 반복
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]👨🏻💻 풀이 과정
해당 문제를 보고 일단 구현을 해보았다.
- 명령확인
reverse()혹은shift()실행
첫번쨰 풀이
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
input.shift();
let answer = '';
const solution = (INPUT) => {
let answer = '';
while (INPUT.length) {
let [Order, N, Arr] = INPUT.splice(0, 3);
const OrderArr = Order.split('');
Arr = JSON.parse(Arr);
answer += `${CHECK(OrderArr, N, Arr)}\n`;
}
console.log(answer);
};
const CHECK = (ORDER, N, ARRAY) => {
for (const RorD of ORDER) {
if (RorD === 'R') {
ARRAY.reverse();
} else {
if (ARRAY.length) {
ARRAY.shift();
} else {
return 'error'
}
}
}
return ARRAY;
};
solution(input);
시간 초과라면 로직 자체가 문제라는 의미로 보였다 그래서 우선 해당 문제의 알고리즘을 확인해 보았다.
나머지는 그냥 그렇게 넘어 갔는데 덱(Deque)이 들어있다.
💡 DEQUE(Double - Ended - Queue)
Deque는 쉽게 말에서 양쪽 모두 뚫려있는 큐를 의미한다.
그럼 해당 문제는 다음과 같은 순서로 진행하면 될 것이다.
- 배열을 덱(Deque)에 저장
- R에 따라 앞 혹은 뒤에서 값을 pop
만약 덱(Deque)이 있을 경우 위와 같은 과정에서
pop은 O(1)의 시간 복잡도를 가질 것이며,
필요에 따라서 배열을 리턴해줄 떄만 배열을reverse해주면 될 것이다.
그러나 JavaScript 에서는 당연히 덱(Deque)을 지원하지 않는다.
우리는 O(n)의 연산인 reverse() 와 shift() 를 최대한 사용하지 않으면서 구현을 해야한다.
따라서 우리는 두 개의 포인터를 이용하여 위의 해당 문제에서 필요한 덱(Deque)을 구현할 것이다.
this.queue에 배열 저장,this.begin에 배열 시작 지점 인덱스 저장this.end에 배열 끝 지점 인덱스 저장this.isReverse로 배열을 뒤집었는지 확인D명령이 들어올 경우this.isReverse값을 확인하고this.begin++혹은this.end--- 만약
this.begin이this.end보다 커지면false를 리턴 아니라면true를 리턴
- 만약
R명령이 들어올 경우this.isReverse변수를 변경slice()를 이용하여 배열 자르기,this.isReverse를 확인후reverse()를 진행한 수 리턴
구현 코드
class DEQUEUE {
constructor(arr) {
this.queue = arr;
this.begin = 0;
this.end = arr.length - 1;
this.isReverse = false;
}
// 현제 값과 반대로 바꿔줌
Reverse() {
this.isReverse = !this.isReverse;
}
Drop() {
// 만약 큐가 비어있는지 확인
if (this.begin <= this.end) {
if (this.isReverse) {
this.end--;
} else {
this.begin++;
}
return true;
} else return false;
}
GetQueue() {
let answer = this.queue.slice(this.begin, this.end + 1);
return this.isReverse ? answer.reverse() : answer;
}
}그리고 메인 함수에서는 DEQUEUE를 선헌 할 때 배열의 형식으로 DEQUEUE에 넣어야한다.
따라서 문자열로 되어 있는 배열을 JavaScript에서 지원하는 자료형으로 바꾸기 위해 JSON.parse를 이용하였다.
"[1,2,3]" 은 split()을 이용하면 괄호까지 들어가기 때문에 JSON.parse 이용
전체적인 로직은 다음과 같이 구성하였다.
- 반복문으로
INPUT에 아무것도 없어질 때까지 반복 splice()를 이용하여INPUT을 3개 단위로 잘라서 확인CHECK함수 내부에서DEQUEUE를 이용하여 값을 받음
메인 함수(solution) 코드
const solution = (INPUT) => {
let answer = '';
while (INPUT.length) {
const [Order, N, InputArray] = INPUT.splice(0, 3);
const OrderArr = Order.split('');
const ARRAY = JSON.parse(InputArray);
answer += CHECK(OrderArr, ARRAY);
}
console.log(answer);
};
const CHECK = (OrderArr, ARRAY) => {
const Dequeue = new DEQUEUE(ARRAY);
for (let i = 0; i < OrderArr.length; i++) {
if (OrderArr[i] === 'R') {
Dequeue.Reverse();
} else if (OrderArr[i] === 'D') {
// 만약 Drop이 될 수 없다면 바로 'error'를 리턴
if (!Dequeue.Drop()) {
return `error\n`;
}
}
}
return `[${Dequeue.GetQueue()}]\n`;
};
solution(input);
전체 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let TestNumber = input.shift();
class DEQUEUE {
constructor(arr) {
this.queue = arr;
this.begin = 0;
this.end = arr.length - 1;
this.isReverse = false;
}
Reverse() {
this.isReverse = !this.isReverse;
}
Drop() {
if (this.begin <= this.end) {
if (this.isReverse) {
this.end--;
} else {
this.begin++;
}
return true;
} else return false;
}
GetQueue() {
let answer = this.queue.slice(this.begin, this.end + 1);
return this.isReverse ? answer.reverse() : answer;
}
}
const solution = (INPUT) => {
let answer = '';
while (INPUT.length) {
const [Order, N, InputArray] = INPUT.splice(0, 3);
const OrderArr = Order.split('');
const ARRAY = JSON.parse(InputArray);
answer += CHECK(OrderArr, ARRAY);
}
console.log(answer);
};
const CHECK = (OrderArr, ARRAY) => {
const Dequeue = new DEQUEUE(ARRAY);
for (let i = 0; i < OrderArr.length; i++) {
if (OrderArr[i] === 'R') {
Dequeue.Reverse();
} else if (OrderArr[i] === 'D') {
if (!Dequeue.Drop()) {
return `error\n`;
}
}
}
return `[${Dequeue.GetQueue()}]\n`;
};
solution(input);🧐 후기
이번 덱(Deque) 문제는 따로 push 연산이 들어가지 않아서 이렇게 구현하여 해결이 되었지만
덱(Deque)의 앞부분에 push 혹은 pop 하는 연산이 O(1)인 점을 이용하여 푸는 문제는 이런 방식으로 풀 수 있을지 의문이 든다.
따라서 그런 문제는 인접 리스트를 이용하여 덱(Deque)을 구현해야 할 것 같다라는 생각이 들었고 해당 덱(Deque)을 직접 구현하는 부분은 좀 더 고민을 해봐야겠다.
