CodingTest/Javascript
[JavaScript] 백준 28279번 덱2
난소히
2024. 5. 10. 12:24
덱이란 ?
문제 요구사항
백준 28279번 덱 2
정수를 저장하는 덱을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여덟 가지이다.
-------------------------------------------------------------------------------
1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
5: 덱에 들어있는 정수의 개수를 출력한다.
6: 덱이 비어있으면 1, 아니면 0을 출력한다.
7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.
-------------------------------------------------------------------------------
첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.
출력을 요구하는 명령은 하나 이상 주어진다.
출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다. -> 무시해도 되는 요구사항이었다.. 뒷부분 참고
첫번째 시도
가장 정석인 push(), pop(), shift(), unshift()를 사용하였다.
역시나 시간 초과로 인한 오류가 발생한다.
shift(), unshift()는 배열을 한 칸씩 옮기기때문에 시간 복잡도가 O(n)로 매우 크다.
const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
function isEmpty(array){
if(array.length < 1){
return true;
}
else{
return false;
}
}
function solution(input) {
let answer = [];
for(let i = 1; i < +input[0] + 1; i++){
if(input[i].length > 1){
let array = input[i].split(' ');
if(array[0] == '1'){ // 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
answer.unshift(+array[1]);
}
else if(array[0] == '2'){ // 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
answer.push(+array[1]);
}
}
else if(input[i].length == 1){
switch(input[i]){
case '3': // 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
if(isEmpty(answer)){
console.log('-1');
}
else{
console.log(answer.shift());
}
break;
case '4': // 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
if(isEmpty(answer)){
console.log('-1');
}
else{
console.log(answer.pop());
}
break;
case '5': // 5: 덱에 들어있는 정수의 개수를 출력한다.
console.log(answer.length);
break;
case '6': // 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
console.log(isEmpty(answer) ? '1' : '0');
break;
case '7': // 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
if(isEmpty(answer)){
console.log('-1');
}
else{
console.log(answer[0]);
}
break;
case '8': // 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.
if(isEmpty(answer)){
console.log('-1');
}
else{
console.log(answer[answer.length - 1]);
}
break;
}
}
}
}
solution(input);
두번째 시도
shift(), unshift()를 사용하지 않기 위해 addFront()와 removeFront()라는 함수를 만들었다.
새로운 배열을 생성하여 공간 복잡도가 높아질 수는 있지만, 백준에서는 시간이 항상 문제이기에 이렇게 작성하였다.
하지만 이번에도 시간 초과로 실패하였다.
const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
function addFront(array, num){
let newArray = [];
if(array.length === 0){
newArray.push(num);
}
else{
newArray = array.map((_, i) => i === 0 ? num : array[i - 1]);
newArray[newArray.length] = array[array.length - 1];
}
return newArray;
}
function removeFront(array){
let newArray = [];
if(array.length === 1){
console.log(array[0]);
}
else{
newArray = array.map((_, i) => array[i + 1]);
newArray.pop();
console.log(array[0]);
}
return newArray;
}
function solution(input) {
let answer = [];
for(let i = 1; i < +input[0] + 1; i++){
if(input[i].length > 1){
let array = input[i].split(' ');
if(array[0] === '1'){ // 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
answer = addFront(answer, +array[1]);
}
else if(array[0] === '2'){ // 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
answer.push(+array[1]);
}
}
else if(input[i].length === 1){
if(['3', '4', '7', '8'].includes(input[i])){
if(answer.length === 0){
console.log('-1');
}
else{
switch(input[i]){
case '3': // 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
answer = removeFront(answer);
break;
case '4': // 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
console.log(answer.pop());
break;
case '7': // 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
console.log(answer[0]);
break;
case '8': // 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.
console.log(answer[answer.length - 1]);
break;
}
}
}
else{
switch(input[i]){
case '5': // 5: 덱에 들어있는 정수의 개수를 출력한다.
console.log(answer.length);
break;
case '6': // 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
console.log(answer.length === 0 ? '1' : '0');
break;
}
}
}
}
}
solution(input);
세번째 시도
배열 내장 함수를 사용하는 것이 문제인가 싶어 Linked List로 구현해보았다.
코드는 복잡해졌지만, array를 사용할 때 보다 채점 퍼센트가 더 올라갔다.
하지만 그럼에도 시간 초과로 실패하였다.
const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class Deque {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
addFront(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
}
else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.size++;
}
addRear(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
}
else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
}
removeFront() {
if (this.isEmpty()) {
return '-1';
}
const removedValue = this.head.value;
if (this.size === 1) {
this.head = null;
this.tail = null;
}
else {
this.head = this.head.next;
this.head.prev = null;
}
this.size--;
return removedValue;
}
removeRear() {
if (this.isEmpty()) {
return '-1';
}
const removedValue = this.tail.value;
if (this.size === 1) {
this.head = null;
this.tail = null;
}
else {
this.tail = this.tail.prev;
this.tail.next = null;
}
this.size--;
return removedValue;
}
printFirst() {
if (this.isEmpty()) {
return '-1';
}
return this.head.value;
}
printLast() {
if (this.isEmpty()) {
return '-1';
}
return this.tail.value;
}
}
function solution(input) {
const deque = new Deque();
for(let i = 1; i < +input[0] + 1; i++){
if(input[i].trim().length > 1){
let array = input[i].trim().split(' ');
if(array[0] === '1'){ // 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
deque.addFront(+array[1])
}
else if(array[0] === '2'){ // 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
deque.addRear(+array[1])
}
}
else if(input[i].trim().length === 1){
switch(input[i].trim()){
case '3': // 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
console.log(deque.removeFront());
break;
case '4': // 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
console.log(deque.removeRear());
break;
case '5': // 5: 덱에 들어있는 정수의 개수를 출력한다.
console.log(deque.size);
break;
case '6': // 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
console.log(deque.isEmpty() ? '1' : '0');
break;
case '7': // 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
console.log(deque.printFirst());
break;
case '8': // 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.
console.log(deque.printLast());
break;
}
}
}
}
solution(input);
마지막 시도 - 성공 !
내 친구 지피티와 상의해본 결과 console.log가 자주 사용되어 시간 복잡도가 높아진다는 피드백을 받았다.
+ 문자열 함수 trim()은 반드시 필요할 때만 사용하라는 피드백도 받았다.
하지만 입력 값을 받을 때 인적 실수를 항상 고려하라는 교수님의 말씀이 떠올라서 ^__^ 제외는 안했다.
그래서 console.log 대신 출력 값을 저장하는 배열을 만들고 마지막에 배열을 출력해주었다.
const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class Deque {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
addFront(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
}
else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.size++;
}
addRear(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
}
else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
}
removeFront() {
if (this.isEmpty()) {
return '-1';
}
const removedValue = this.head.value;
if (this.size === 1) {
this.head = null;
this.tail = null;
}
else {
this.head = this.head.next;
this.head.prev = null;
}
this.size--;
return removedValue;
}
removeRear() {
if (this.isEmpty()) {
return '-1';
}
const removedValue = this.tail.value;
if (this.size === 1) {
this.head = null;
this.tail = null;
}
else {
this.tail = this.tail.prev;
this.tail.next = null;
}
this.size--;
return removedValue;
}
printFirst() {
if (this.isEmpty()) {
return '-1';
}
return this.head.value;
}
printLast() {
if (this.isEmpty()) {
return '-1';
}
return this.tail.value;
}
}
function solution(input) {
const deque = new Deque();
const answer = [];
for(let i = 1; i < +input[0] + 1; i++){
if(input[i].trim().length > 1){
let array = input[i].trim().split(' ');
if(array[0] === '1'){ // 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
deque.addFront(+array[1])
}
else if(array[0] === '2'){ // 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
deque.addRear(+array[1])
}
}
else if(input[i].trim().length === 1){
switch(input[i].trim()){
case '3': // 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
answer.push(deque.removeFront());
break;
case '4': // 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
answer.push(deque.removeRear());
break;
case '5': // 5: 덱에 들어있는 정수의 개수를 출력한다.
answer.push(deque.size);
break;
case '6': // 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
answer.push(deque.isEmpty() ? '1' : '0');
break;
case '7': // 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
answer.push(deque.printFirst());
break;
case '8': // 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.
answer.push(deque.printLast());
break;
}
}
}
console.log(answer.join('\n'));
}
solution(input);
결과 값을 한번에 출력해도 되는거면
이런 요구사항은 왜 있는 건지..ㅎㅎ
알 수 없는 백준
++
혹시 console.log 때문에 계속 오류가 난건가 하여 두번째 시도 + 결과 값 배열 저장하여 출력해보았는데 역시나 시간 초과가 발생한다 ^^