지수의 블로그

2 분 소요

[알고리즘]

백준 알고리즘 문제풀이

자료구조 - 큐

10845 (큐) (feat. 18258 (큐2))

  • 문제

  • 입출력

  • 입력 예제

  • 출력 예제

그냥 큐를 구현하면 되는 문제이다.

사실 글을 남겨놓는 이유는 따로 있다….

원래는 18258번 큐2를 풀고 있었는데, 다 풀고 VScode는 잘 돌아가고 답도 나오는 것이

제출하면 자꾸 시간초과가 떠서 절망했다.

심지어 검색하면 Javascript는 잘 나오지도 않는다.

그래서 어떻게 문제를 접근하게 되었느냐면,

애초에 백준 문제들이 nodeJS에 굉장히 불친절하다.
<br>심지어 ES6의 모든 문법을 지원하는 것도 아니고,(채점 오류 때문에 map, reduce, filter를 쓰지 않는 것을 추천한다고 한다는데..), 입력값 받는 것 자체도 곤욕이다. (초보자 진입장벽이 매우 높다.)

어쨌든 이런 상황에서 알고리즘 스터디에서 한 분이 ES6 문법 때문에 고생하는 것을 바로 엊그저께 보았다.
<br>그래서 아, 백준은 내가 원하는 대로 문법 쓰면 만사오케이가 되지는 않겠구나 생각했다.

다시 큐 문제로 돌아와서

아무리 봐도 내가 쓴 메서드 중에 느릴 것 같은 애가 push, shift 정도였다.
그래서 javascript shift를 쳐보니 애초에 O(n)의 시간복잡도를 갖는 친구였더라..

확실히 이 친구가 문제라는 것을 깨달았는데

이제는 문제 자체를 어떻게 푸냐는 것이다.(shift 안쓰면 pop 어떻게 구현할건데)

나는 설마했다. 첫번째 요소를 삭제함에 있어서 가장 간단한 방법은 SingleLinkedList를 사용하는 것인데, 큐 문제에서 갑자기 이것을 요구할지는 몰랐다. (아니 단계별 문제인데, 장난하냐거ㅡㅡ)

설마가 사람잡는다고 검색해보니 javascript로 푸는 경우에 만약 문제에서 큐에 요소 추가/삭제가 많을 것 같다하면 linked list로 구현을 해야한다고 하더라.


그래서 내가 어떻게 했냐면






안풀었다.

차근차근 자료구조 공부해가면서 순서대로 풀 것이다.

그래서 이미 푼 이 문제는 테스트 케이스가 많지 않은 똑같은 문제 10845번 큐 문제를 풀었고, 바로 정답을 얻었다.


  • 내가 푼 것
const fs = require("fs");
let input =
  process.platform === "linux" //
    ? fs.readFileSync("/dev/stdin").toString().split("\n")
    : fs.readFileSync("Baekjoon/input.txt").toString().split("\n");

const queue = [];
const C = input.shift();

let result = "";

for (let i = 0; i < C; i++) {
  switch (input[i].split(" ")[0].toString().trim()) {
    case "pop":
      result += `${queue[0] ? queue[0] : -1}\n`;
      queue.shift();
      break;
    case "size":
      result += `${queue.length}\n`;
      break;
    case "empty":
      result += `${queue.length === 0 ? 1 : 0}\n`;
      break;
    case "front":
      result += `${queue[0] ? queue[0] : -1}\n`;
      break;
    case "back":
      result += `${queue[queue.length - 1] ? queue[queue.length - 1] : -1}\n`;
      break;
    default:
      queue.push(Number(input[i].split(" ")[1]));
      break;
  }
}
console.log(result);

그냥 직관적인 문제였다.

입력을 잘 가져와서 써먹는 것 주의하면서 (\r 붙어 있는지, number 형 잘 변환되었는지 등등) 커맨드마다 각각 구현해주면 되는 것.

아, 시간을 좀 더 줄이기 위해 case 문에 바로바로 console을 넣지 않았다.

이렇게 하면 시간 더 많이 든다고 하니 항상 시간이 많이 들 것 같은 문제는 result 문자열을 선언해서 추가한다.

다행인게 구현한 거 못 써먹나 싶었는데, 같은 문제가 있어서 너무 다행이었다. ㅠㅠ

다음에는 좀 더
함수 조심
문법 조심
그리고 나의 알고리즘/자료구조 개념(시간복잡도를 모른 것도 죄)
을 더 공부해야 겠다.

댓글남기기

참고