[바미] 도키도키 간식드리미

문제

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

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = parseInt(input[0], 10);
const students = input[1].split(' ').map(Number);

const stack = [];
let next = 1;  // 다음으로 간식을 받아야 하는 학생의 번호

students.forEach(student => {
    while (stack.length > 0 && stack[stack.length - 1] === next) {
        stack.pop();
        next++;
    }
    if (student === next) {
        next++;  // 현재 번호 학생이 순서대로 간식을 받을 수 있으면 다음 번호로 넘어간다
    } else {
        stack.push(student);  // 아니면 스택에 임시 대기
    }
});

// 스택에 남아있는 학생들을 확인
while (stack.length > 0) {
    if (stack.pop() !== next) {
        console.log("Sad");
        return;
    }
    next++;
}

console.log("Nice");

코드 설명

const N = parseInt(input[0], 10);
const students = input[1].split(' ').map(Number);

const stack = [];
let next = 1;  // 다음으로 간식을 받아야 하는 학생의 번호​

여기서 학생의 수를 저장하는 N,

학생들의 번호 순서가 주어진 students배열,

순서를 확인하기 위해 임시로 사용될 stack 변수를 초기화 해줍니다.

 

students.forEach(student => {
    while (stack.length > 0 && stack[stack.length - 1] === next) {
        stack.pop();  // 스택의 최상단 학생이 순서대로 간식을 받을 수 있다면 스택에서 제거
        next++;       // 다음 순서의 학생으로 넘어갑니다
    }
    if (student === next) {
        next++;      // 현재 학생이 바로 간식을 받을 수 있다면 다음 학생으로 넘어갑니다
    } else {
        stack.push(student);  // 순서가 맞지 않으면 스택에 임시 대기
    }
});

각 학생을 확인하며, 스택을 사용해 순서대로 처리할 수 있는지를 판단해줍니다.

스택의 최상단 학생이 올바른 순서인 경우, 스택에서 제거하고 다음 순서로 넘어가며, 그렇지 않은 경우 스택에 학생을 추가합니다.

 

// 스택에 남아있는 학생들을 확인
while (stack.length > 0) {
    if (stack.pop() !== next) {
        console.log("Sad"); // 스택에 남은 학생이 순서대로 간식을 받을 수 없다면 "Sad" 출력
        return;
    }
    next++;
}

스택에 남아있는 학생들이 올바른 순서로 남아있는지 확인합니다. 

 

그 후 

console.log("Nice");  // 모든 검사를 통과하면 "Nice" 출력

모든 검사를 통과하게 되면 결과를 출력해줍니다.

문제 해설

주어진 번호표 순서대로 학생들이 간식을 받을 수 있는지 확인하는 문제입니다.

스택을 사용하여 대기열에 있는 사람들이 임시로 대기할 수 있는 공간으로 활용하여 풀었습니다.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

N은 승환이 앞에 있는 학생들의 수로 제가 작성한 코드는 모든 학생에 대해 push 또는 pop 연산을 한 번씩 처리하도록 되어있습니다. 이러한 연산들은 상수 시간 O(1)이 걸리게 되고, 모든 학생을 한 번씩 확인하는 데 총 N번의 연산이 필요하므로 시간 복잡도는 O(N)이 됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

학생 번호가 역순으로 주어진 경우 (N, N-1, ..., 2, 1) 스택은 각 번호를 임시로 저장해야 하는 최악의 경우가 있어 공간 복잡도는 O(N)이 됩니다.

이 때 각 학생 번호는 스택에 push되고 순서대로 간식을 받을 수 있을 때까지 스택에 남아 있게 되는데 스택이 사용할 수 있는 최대 공간은 학생의 수 N에 비례하게 됩니다.