백준 - 알고리즘 기초 1/2 ( 200 - 자료구조 1 )

백준 알고리즘 기초 1/2

1. 10828번 - 스택

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[0] === input.length - 1) rl.close();
}).on("close", () => {
  input.shift();

  let index = 0;
  const array = [];
  const stack = {
    push(item) {
      array[index++] = item;
    },
    pop() {
      if(array.length === 0)  return -1
      const [item] = array.splice(--index, 1);
      return item;
    },
    size() {
      return array.length;
    },
    empty() {
      return array.length === 0 ? 1 : 0;
    },
    top() {
      return array[index - 1] || -1;
    }
  };

  
  let answer = "";

  input.forEach(v => {
    const x = v.split(" ");
    if (x[0] === "push") {
      return stack[x[0]](x[1]);
    }
    
    answer += `${stack[v]()}\n`;
  });
  
  console.log(answer);

  process.exit();
});

2. 9093번 - 단어 뒤집기

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[0] === input.length - 1) rl.close();
}).on("close", () => {
  input.shift();

  let answer = "";

  input.forEach(value => {
    value.split(" ").forEach(v => {
      answer += `${v.split("").reverse().join("")} `;
    });
    answer += "\n";
  });

  console.log(answer);

  process.exit();
});

3. 9012번 - 괄호

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// stack
let index = 0;
let array = [];
const stack = {
  push(item) {
    array[index++] = item;
  },
  pop() {
    if (array.length === 0) return -1;
    const [item] = array.splice(--index, 1);
    return item;
  },
  size() {
    return array.length;
  },
  empty() {
    return array.length === 0 ? 1 : 0;
  },
  top() {
    return array[index - 1] || -1;
  },
};

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[0] === input.length - 1) rl.close();
}).on("close", () => {
  input.shift();

  let answer = "";

  input.forEach(value => {
    const result = value.split("").some(v => {
      switch (v) {
        case "(":
          stack.push("(");
          break;
        case ")":
          // 스택이 이미 비어있다면 짝이 안맞음
          if (stack.empty()) return true;
          // 이전에 입력한 괄호가 닫는괄호라면 짝이 안맞음
          if (stack.top() === ")") return true;
          stack.pop();
          break;

        default:
          break;
      }
      return false;
    });

    // 다 끝났는데 스택이 비어있지 않다면 짝이 안맞음 ( 다음 반복을 위해 초기화함 )
    if (stack.empty()) answer += `${result ? "NO" : "YES"}\n`;
    else {
      answer += "NO\n";
      array = [];
      index = 0;
    }
  });

  console.log(answer);

  process.exit();
});

4. 1874번 - 스택 수열

아니 문제가 이해가 안가요...

5. 1406번 - 에디터

최초에는 Array.prototype.splice()를 이용해서 cursor값을 가지고 배열의 중간을 자르고 추가하는 방식으로 구현을 했습니다.

하지만 그 방식을 이용하면 시간초과를 만나게 되는데 이유를 추측해보자면 splice()를 이용해서 배열을 컨트롤하게 되면, 중간에 삽입 or 삭제 연산을 실행하는 경우 중간 이후의 모든 부분을 다시 재조정 해줘야하는 연산이 필요하므로 시간초과가 나온다고 생각합니다.

따라서 배열에서 가장 빠르고 간단하게 처리할 수 있는 연산인 Array.prototype.push()와 Array.prototype.pop()을 이용해서 구현을 하면 해결됩니다.

• 백준 1406 nodejs 참고

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[1] === input.length - 2) rl.close();
}).on("close", () => {
  const lStack = input.shift().split("");
  const rStack = [];
  input.shift();

  input.forEach(value => {
    const [command, char] = value.split(" ");

    switch (command[0]) {
      case "L":
        if (lStack.length === 0) break;
        rStack.push(lStack.pop());
        break;
      case "D":
        if (rStack.length === 0) break;
        lStack.push(rStack.pop());
        break;
      case "B":
        lStack.pop();
        break;
      case "P":
        lStack.push(char);
        break;
      
      default:
        break;
    }
  });
  
  let answer = lStack.join("") + rStack.reverse().join("");

  console.log(answer);

  process.exit();
});

6. 10845번 - 큐

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
let queue = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[0] === input.length - 1) rl.close();
}).on("close", () => {
  input.shift();

  const commandList = [...input];

  let answer = "";

  commandList.forEach(value => {
    const [command, v] = value.split(" ");

    switch (command) {
      case "push":
        queue.push(v);
        break;
      case "pop":
        const number = queue.shift();
        answer += `${number ? number : -1}\n`;
        break;
      case "size":
        answer += `${queue.length}\n`;
        break;
      case "empty":
        answer += `${queue.length === 0 ? 1 : 0}\n`;
        break;
      case "front":
        answer += `${queue[0] ? queue[0] : -1}\n`;
        break;
      case "back":
        answer += `${queue[queue.length - 1] ? queue[queue.length - 1] : -1}\n`;
        break;
    
      default:
        break;
    }
  })

  console.log(answer);

  process.exit();
});

7. 1158번 - 요세푸스 문제

처음에 Array.prototype.push와 Array.prototype.pop을 이용해서 풀어보려고 했지만, 계속 index값이 불일치해져서 shift사용함

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  rl.close();
}).on("close", () => {
  const [N, K] = input[0].split(" ").map(v => +v);

  const people = new Array(N).fill().map((v, i) => i + 1);

  const answer = [];
  
  // Queue의 원리를 이용해서 푸는 문제임
  let count = 0;
  while (people.length) {
    count++;

    // 지정된 횟수의 사람이면 제거
    if (count === K) {
      answer.push(people.shift());
      count = 0;
    }
    // 그게 아니라면 다시 맨뒤로 넣음
    else {
      people.push(people.shift());
    }
  }

  console.log("<" + answer.join(", ") + ">");

  process.exit();
});

8. 10866번 - 덱

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[0] === input.length - 1) rl.close();
}).on("close", () => {
  input.shift();

  const deque = [];
  let answer = "";

  input.forEach(v => {
    const [command, value] = v.split(" ");
    let temp = null;

    switch (command) {
      case "push_front":
        deque.unshift(value);
        break;
      case "push_back":
        deque.push(value);
        break;
      case "pop_front":
        temp = deque.shift() || -1;
        answer += `${temp}\n`;
        break;
      case "pop_back":
        temp = deque.pop() || -1;
        answer += `${temp}\n`;
        break;
      case "size":
        answer += `${deque.length}\n`;
        break;
      case "empty":
        temp += deque.length === 0 ? 1 : 0;
        answer += `${temp}\n`;
        break;
      case "front":
        temp = deque[0] || -1;
        answer += `${temp}\n`;
        break;
      case "back":
        temp = deque[deque.length - 1] || -1;
        answer += `${temp}\n`;
        break;

      default:
        break;
    }
  });

  console.log(answer);

  process.exit();
});