[백준] 12789 : 도키도키 간식드리미 (스택)

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

 

 

Code 

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' 출력 여부를 결정합니다.

 

 

 

 

 

 

 

src : https://arnopark.tistory.com/832