[백준] 10773번 : 제로 - C/C++

문제 풀이 순서는 아래와 같다.

1. 입력할 숫자의 개수 k 입력

2. k개만큼의 수 입력 받기 (0을 입력했다면 최근에 입력한 수 지우기)

3. 입력을 완료했다면 남아있는 수 출력하기

 

최근에 입력한 수를 지우는 방법은 stack을 사용하면 된다.

스택은 LIFO의 형태이기 때문에 0을 push 했을 경우에,

두 번 pop 해주면 된다.

 

그렇게 코드를 작성해보자.

스택을 사용하기 위해서는 헤더를 추가해주어야 한다.

#include <stack>

 

입력받을 개수 k를 입력 받았다고 가정하고,

스택을 구현하자.

stack<int> st;

for(int i=0;i<k;i++){
   cin >> n;
   if(n == 0){
   if(!st.empty()){
     st.pop();
   }
 } else {
   t.push(n);
  }
}

 

스택을 이렇게 간단하게 구현할 수 있다!

0을 입력했을 때의 조건도 추가해주면 된다.

 

그럼 합은 어떻게 구하나요?

위에서 말했듯이 스택은 LIFO 구조이기 때문에

필자는 하나씩 pop을 해주면서 더하는 방법을 택할 것이다.

 

코드로 작성하면 아래와 같다.

int sum = 0;

while(!st.empty()){        
  sum += st.top();
  st.pop();
}

 

간단하다.

 

 

 

전체 코드

#include <iostream>
#include <stack>

//제로
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);

    int k,n;
    cin >> k;
    stack<int> st;

    for(int i = 0; i < k; i++){
        cin >> n;
        if(n == 0){
            if(!st.empty()){
                st.pop();
            }
        } else {
            st.push(n);
        }
    }
    int sum = 0;
    while(!st.empty()){        
        sum += st.top();
        st.pop();
    }
    cout << sum << '\n';

    return 0;
}

 

 

실버4의 문제였다. 앞서 공부했던(풀었던) 글들을 본다면 이번 문제는 기본 문제에 속한다는 것을 쉽게 알아차릴 수 있을 것이다.

자료구조나 스택 등의 알고리즘 문제는 보통 난이도가 실버 이상인 것 같다. 실버 난이도는 풀기도 전에 당황하고 들어가는 것 같은데, 이런 기본 문제부터 차근차근 풀어나가면 실버는 물론 골드 난이도의 문제까지도 풀어나갈 수 있을 것이다.

 

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️