[백준 / C, C++] Day5. 제로 (10773)

2024. 05. 22 - 코딩테스트 스터디 Day5

 

 

01. 문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

 

 

02. 입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

 

 

03. 출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 2³¹-1보다 작거나 같은 정수이다.

 

 

04-1. 예제 입력 1

4
3
0
4
0

 

 

04-2. 예제 출력 1

0

 

 

05-1. 예제 입력 2

10
1
3
5
4
0
0
7
0
0
6

 

 

05-2. 예제 출력 2

7

 

 

06-1. 풀이 및 답 - C언어

#include <stdio.h>

int main() {
    int k, n;
    int arr[1000000];
    int size = -1;
    int answer = 0;
    scanf("%d", &k);
    
    for (int i=0; i<k; i++) {
        scanf("%d", &n);
        if (n == 0) {
            arr[size--] = 0;
        }
        else {
            arr[++size] = n;
        }
    }
    for (int i=0; i<=size; i++) {
        answer += arr[i];
    }
    
    printf("%d", answer);
    return 0;
}

스택을 활용하여 문제를 해결해 주었다.
k값을 입력받아 k만큼 반복하며 n을 입력받는다.

이때 n이 0이라면 가장 최근의 값, 즉 스택의 top 값을 0으로 덮어쓴다.

n이 0이 아니라면 n을 스택의 최상위에 push 해준다.

k만큼 반복한 후, 스택에 있는 모든 데이터 값들을 answer라는 변수에 더해주었다.

 

 

answer에 스택 데이터 값들을 더해줄 때 반복문을 

for (int i=0; i<size; i++)

이렇게 작성해서 한번 틀렸다.

위 코드에서의 size는 0부터 시작하는 배열의 인덱스와 마찬가지이다. 실제 스택 사이즈는 size+1이라는 것을 명심하자.

스택 관련 문제 풀 때마다 size에서 자꾸 헷갈리게 되는 것 같다. 주의해야겠다!

 

 

정답!

 

 

06-2. 풀이 및 답 - C++

어제와 마찬가지로 C++로도 코드를 짜보았다.

#include <iostream>
#include <stack>
using namespace std;

int main() {
    int k, n;
    stack<int> stack;
    int answer = 0;
    
    cin >> k;
    for (int i=0; i<k; i++) {
        cin >> n;
        if (n == 0) {
            stack.pop();
        }
        else {
            stack.push(n);
        }
    }
    
    int size = stack.size();
    for (int i=0; i<size; i++) {
        answer += stack.top();
        stack.pop();
    }
    
    cout << answer << "\n";
}

n이 0이면 pop, 0이 아니면 n값을 push 하도록 코드를 작성했다.

 

answer에 스택의 모든 데이터 값들을 저장하는 과정에서 아무 생각 없이 for문을

for (int i=0; i<stack.size(); i++)

이렇게 작성해서 한 번 틀렸다. 반복문을 돌면서 스택 데이터 값이 pop 되어 스택의 size가 점점 줄어들기 때문에 이렇게 코드를 작성하면 틀린다. 주의하도록 하자!

 

역시 정답!