[바미] 제로

문제

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

코드

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

const K = parseInt(input[0], 10);
const stack = [];

for (let i = 1; i <= K; i++) {
    const num = parseInt(input[i], 10);
    if (num === 0) {
        stack.pop(); // 0이 입력되면 스택의 최상위 요소(가장 최근의 수)를 제거
    } else {
        stack.push(num); // 0이 아닌 수는 스택에 추가
    }
}

// 스택에 남아있는 모든 수의 합을 계산
const sum = stack.reduce((acc, curr) => acc + curr, 0);

// 결과 출력
console.log(sum);

문제 해설

이 문제는 스택을 활용하여 지정된 명령에 따라 숫자를 추가하거나 제거하고, 최종적으로 남은 숫자들의 합을 계산하는 문제입니다.

입력된 숫자가 0이면 가장 최근에 입력된 숫자를 삭제하고, 그렇지 않은 경우 입력된 숫자를 스택에 추가해야 하죠.

 

문제 아래에 힌트가 있어 참고하실 때 많은 도움이 되실 겁니다.

예제 2의 경우를 시뮬레이션 해보면,

[1]
[1,3]
[1,3,5]
[1,3,5,4]
[1,3,5] (0을 불렀기 때문에 최근의 수를 지운다)
[1,3] (0을 불렀기 때문에 그 다음 최근의 수를 지운다)
[1,3,7]
[1,3] (0을 불렀기 때문에 최근의 수를 지운다)
[1] (0을 불렀기 때문에 그 다음 최근의 수를 지운다)
[1,6]
합은 7이다.

 

시간 복잡도

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

 

 스택에 숫자를 push하거나 pop 하는 등의 각 명령은 일반적으로 상수 시간 O(1)이 소요되기 때문에 K개의 명령을 처리하는데 각 명령 시간 O(1)에 명령 수 K를 곱한 O(K)이 됩니다. 이는 프로그램의 실행 시간은 명령의 수에 직접 비례합니다.

 

여기서 K는 스택에 적용할 명령의 총 개수를 의미합니다.

공간 복잡도

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

 

모든 명령이 숫자를 스택에 저장하는 명령일 경우 스택은 최대 K개의 숫자를 저장할 수 있습니다. 여기서 0명령은  스택에서 숫자를 제거하지만 모든 숫자를 저장하는 경우의 공간 사용량은 최대 K가 됩니다.

 

따라서 공간복잡도는 O(K)로 표현 할 수 있고, 입력으로 주어진 명령 수에 비례하는 최대 메모리 사용량을 의미합니다.

 

여기서 K는 주어진 명령의 수이면서 스택에 저장될 수 있는 숫자의 최대 개수를 가리킵니다.