[BOJ] 백준 10773번: 제로 (C++)

 

- 문제 출처 : https://www.acmicpc.net/problem/10773

---

1. 생각

3번째로 가져온 문제도 스택 문제를 가져와봤다.

최근에 코딩 테스트 문제를 풀기 위해 java를 처음 사용해봤는데,

확실히 언어에 대한 이해도가 낮아 문제를 푸는데도 너무 오래 걸리고

여전히 C 스타일로 많이 짜게 되는 경향이 있어 C++을 사용해서 문제를 풀어야하나 고민이 있었다.

 

고민의 결론은, 기존에 C를 많이 사용했던터라, C++ 로 먼저 객체지향 언어를 익숙하게 사용해본 뒤,

Java로 넘어가서 조금 더 쉽게 언어를 익히는 게 좋을 것 같다는 결론이 나왔다.

따라서 이번 문제부터는 C++로 푸는 것으로 결정!

 

우선 이번 문제는 '재민'이라는 인물이 장부에 수를 적는 역할,

'재현'이라는 인물이 장부에 적힌 마지막 수를 지우는 역할로 등장한다.

 

따라서 스택이라는 자료구조를 사용한다는 것을 알아차리게 된다면,

재민은 push / 재현은 pop의 역할을 한다는 것을 짐작할 수 있다.

일반 숫자가 오면 해당 숫자를 push, 0이 오면 가장 최신의 숫자를 pop해서 비우면 될 듯 하다.

 

2. 난관 & 해결 방법

#include <iostream>
#include <stack>

 

C++ 에서는 stack 자료구조를 템플릿 라이브러리를 통해 사용할 수 있다.

그를 위해 #include <stack> 을 작성해준다.

 

std::stack<int> st;

 

stack을 선언하는 방법은 stack 뒤에 '<자료형> + 이름'을 작성해주면 해당 자료형의 스택을 만들 수 있다.

템플릿 라이브러리를 사용하니 상당히 간단하게 만들 수 있다.

물론 이전 문제들처럼 직접 배열로 만들어도 되지만, 이번엔 라이브러리를 활용해보았다.

 

std::cin >> n;
for (int i = 0; i < n; i ++){
    std::cin >> cost;
    if (cost == 0)
        st.pop();
    else
        st.push(cost);
}
while (st.empty() == 0){
    sum += st.top();
    st.pop();
}
std::cout << sum;

 

0이 입력되었을 때를 제외하고는 모두 push해서 담고, 0일시에는 pop으로 빼버린다.

그 이후 만들어진 스택을 empty()를 이용해 텅 빌때까지 top의 값을 sum에 쌓고, pop하는 과정을 거치면

이번 문제를 간단하게 해결할 수 있다.

 

자, C++에서는 위와 같이 std::cin 과 std::cout 으로 입출력을 사용한다.

하지만 이 방식은 C에서의 printf, scanf 보다 느리다고 하는데, 이를 극복하기 위해서 방법이 하나 있다.

 

std::ios::sync_with_stdio(false);

 

이 줄을 하나 추가해준다면,

 

(위 : 한줄을 추가한 코드 / 아래 : 기존 코드)

 

2배 이상 시간이 빨라진 것을 확인할 수 있다.

이 코드는 동기화를 비활성화하여 속도를 증가시키는 것인데,

싱글 스레드 상황에서만 사용할 수 있어 일종의 편법처럼 사용한다고 한다.

 

이번 문제는 반복이 적어서 영향은 없겠지만 좀 더 큰 문제들에서는 필요할 수도 있으니 알아두자.

 

3. 코드 및 결론

[ 전체 코드 ]

#include <iostream>
#include <stack>

int main(){
    std::stack<int> st;
    int n, cost, sum = 0;
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    for (int i = 0; i < n; i ++){
        std::cin >> cost;
        if (cost == 0)
            st.pop();
        else
            st.push(cost);
    }
    while (st.empty() == 0){
        sum += st.top();
        st.pop();
    }
    std::cout << sum;
    return (0);
}

 

[ 결론 ]

 

이번에는 C++과 C++ STL(Standard Template Library)의 stack 을 활용하여 문제를 풀어보았다.

문제 자체는 너무 쉬웠지만 또 새롭게 알아가는 정보들이 많아 유익했다.

확실히 C를 자주 써서 그런지 더 익숙하고 편한 감이 없지 않아 있다.

 

추후 C++ 문제 푸는게 많이 익숙해진 뒤에는 Java로도 문제를 풀어보도록 하겠다.