백준 10773번(스택): 제로

 

문제

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

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

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

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

입력

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

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

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

출력

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

 

나의 답

#include <iostream>
#include <string>
#define SIZE 100000
using namespace std;

struct  stack{
    int top=-1;
    int arr[SIZE];
};
void push(struct stack *S, int n){
    if(S->top==SIZE-1){

    }else {
        int top;
        S->top +=1;
        top = S->top;
        S->arr[top] = n;
    }
}

int pop(struct stack *S){
    if(S->top==-1){
        return 0;
    }else {
        int temp;
        int top = S->top;
        temp = S->arr[top];
        S->top = S->top -1;
        return temp;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    struct stack S;
    int input=0,num=0;
    int i,del=0,all=0;
    cin>>num;
    
    for(i=0;i<num;i++){
        cin>>input;
        
        if(input!=0){
            push(&S,input);
            all+=input;
        }else if(input==0){
           del+= pop(&S);
        }
    }
    cout<<all-del<<endl;
    return 0;
}

if문을 두고 값을 입력받을 때마다 0인지 아닌지 판별한다. 

0이라면 삭제, 0이 아니라면 push. 

 

정답 판정을 받기 전에 3번정도의 오류가 있었는데, 그 이유는 다음과 같다. 

   실패의 원인 1

이전의 stack 코드 ( 10828?이었을 듯 단계별 문제>스택>첫번째문제) 에서 짰던 스택 코드를 이용해서 이 문제를 해결했는데, 그 전에 코드에서 

int pop(struct stack *S){
    if(S->top==-1){
        return -1; // 이 곳이 문제!!
    }else {
        int temp;
        int top = S->top;
        temp = S->arr[top];
        S->top = S->top -1;
        return temp;
    }
}

라고 작성한 것을 이번 문제에서 그대로 활용한 것이 문제가 되었던 것이다.  

입력을 3,0,0,0 으로 했을 때 값이 0이 나와야 하는데, 다른 값이 나왔다.

위의 잘못된 부분이라고 주석으로 표시 해 놓은 곳에서 알 수 있듯이 

pop에서 배열이 비어있을 때(==top이 -1일때) -1을 반환을 하도록 해서 

3,0,0,0 의 입력값일 경우 비어있는 배열에 대한 리턴값이 계산이 되고 있는 상황인 것으로 보인다. 

위의 문제가 있는 부분을 return 0; 으로 변경하였더니 문제가 해결되었다. 

 

 

실패의 원인 1을 해결하고 입력,출력값을 넣어보니 정상적으로 출력이 된다. 하지만 계속 채점 결과는 오답이었다. (저번 스택 구현 문제의 악몽이 떠올랐다.)

 

하지만 생각보다 그 이유는 간단했다. 

 

   실패의 원인 2

 

우선 문제를 보자. 다음과 같이 명시되어있다. 

 

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

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며...!!!!

 

첫 번째 줄에 입력하는 정수는 내가 몇 개의 라인을 입력할건지에 대한 수를 쓰는 것이기 때문에

(1 ≤ K ≤ 100,000) 사이의 값을 가진다면 100000 을 받아서 100000 번 for문을 돌려야 할 것이다. 

그렇기 때문에 당연히 struct 의 구성 요소인 스택 배열 또한 최대 100000 개를 받을 수 있어야 할 것이다. 

 

이전 코드를 그대로 가져와서 사용했기 때문에 100으로 define 되어 있는 상황이었다. SIZE를 100000으로 수정하고 제출하니 채점 결과가 정답으로 나왔다!

 

오늘의 교훈...

1. 문제를 잘 읽자

2. 다른 코드를 이용해서 문제를 풀 때 값들을 한번 더 확인 해 주자!! 방심 금지!!