[백준/JS] 12789. 도키도키 간식드리미

안녕하세요. 박기린 입니다.

백준 12789번 도키도키 간식드리미 문제를 풀어보겠습니다.

 

---

문제 링크

https://www.acmicpc.net/problem/12789

12789번: 도키도키 간식드리미

 

 

 

 

 

 

---

문제 해석

Input 배열 : 백준 문제에서 준 입력값을 담은 배열. 큐 구조를 이용할 예정입니다.

Stack 배열 : 임시로 줄 선 사람을 옮겨둘 수 있는 공간

cur : 간식을 받을 차례

 

위 3가지를 먼저 염두에 둡니다.

 

 

 

 

가장 먼저 1번 순서가 받을 차례이기 때문에 cur을 1로 설정합니다.

Input배열에서 1이 나올 때까지, Stack 배열로 deque & push를 합니다.

 

1이 나오면, Input에서 pop을 하고 버립니다.

 

 

 

 

 

다음 순서는 2번입니다. Input의 top이 2가 될 때까지, Stack으로 deque & push 합니다.

2가 나오면 pop하고 버립니다.

 

 

 

 

 

이제 Input 배열에는 아무 요소가 없으니 버리고, Stack 배열을 살핍니다.

3번째 순서가 간식을 받을 차례입니다. Stack 배열을 pop 했을 때, cur와 일치한 숫자가 나온다면 계속 이 과정을 반복하고, 만약 다른 숫자가 나온다면 반복을 중지합니다. 그리고 'Sad'를 출력합니다.

 

위 예제는 동일한 3이 나왔으니, 이 과정을 다시 반복합니다.

 

 

 

 

4, 5까지 전부 마치고, 모든 순서가 알맞게 간식을 받았다는 것이 확인되면, 'Nice'를 출력합니다.

 

 

 

 

---

정답 코드

const fs = require("fs");
const [n, INPUT] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const input = INPUT.split(" ").map(Number);
const stack = [];
let top = 0;
let cur = 1;
let output = "";

input.forEach((e) => {
  while (stack[top - 1] === cur) {
    stack.pop();
    top--;
    cur++;
  }

  if (e !== cur) {
    stack.push(e);
    top++;
  } else {
    cur++;
  }
});

while (stack.pop() === cur) {
  top--;
  cur++;
}

top === 0 ? (output = "Nice") : (output = "Sad");
console.log(output);

 

 

 

 

---

정답 코드 풀이

const fs = require("fs");
const [n, INPUT] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const input = INPUT.split(" ").map(Number);
const stack = [];
let top = 0;
let cur = 1;
let output = "";

 

fs 모듈로 입력을 받습니다.

문제 해석 섹션에서 말씀드린 input배열, stack배열, cur을 생성합니다.

추가로 stack 배열의 top 요소를 접근하기 위한 top 변수도 선언합니다.

 

 

 

input.forEach((e) => {
  while (stack[top - 1] === cur) {
    stack.pop();
    top--;
    cur++;
  }

  if (e !== cur) {
    stack.push(e);
    top++;
  } else {
    cur++;
  }
});

input 배열은 forEach 문을 이용해서 차례대로 요소를 접근합니다.

 

 

 

  while (stack[top - 1] === cur) {
    stack.pop();
    top--;
    cur++;
  }

forEach 문을 돌던 중, 만약 stack의 top에 cur과 동일한 요소가 들어가 있다면, stack을 pop하는 반복문입니다.

Input 배열에서 cur 변수가 수정되다가, stack의 top과 일치하는 값이 나타날 수 있기 때문입니다.

 

 

  if (e !== cur) {
    stack.push(e);
    top++;
  } else {
    cur++;
  }

forEach 문을 돌 때, 현재 접근중인 요소가 cur과 동일하다면 stack에 집어넣지않고 무시한 채 cur++만 해줍니다. (deque)

만약 동일하지 않다면, stack에 push하고 top++를 해줍니다.

 

 

 

while (stack.pop() === cur) {
  top--;
  cur++;
}

 

input 배열을 forEach 문으로 모두 돌고, stack 배열만 남은 상태일 때 작동하는 코드입니다.

stack의 top이 cur과 동일하다면, 계속 pop을 진행하고, 아니면 반복을 종료합니다.

 

 

 

 

top === 0 ? (output = "Nice") : (output = "Sad");
console.log(output);

만약 반복이 중간에 끊겼다면 top은 양의 정수일 것이고, 반대로 모든 반복을 마치고 stack의 길이가 0이 됐다면 top도 0이 될 것입니다.

따라서 top이 0인 여부에 따라 'Nice'와 'Sad' 출력 여부를 결정합니다.