[BaekJoon 10773][⚪4] 제로

❓ 문제

백준 10773 - “제로”

🎯 난이도

Silver ⚪4

🧠 풀이

1. 내 풀이 (stack)

- 알고리즘

• Data Structure, stack

- 설명

stack을 사용해 해결한 풀이이다.

일반적인 stack 문제처럼 풀었다. 또한 한가지 미세한 최적화도 들어가 있다.

Sum을 구하는 과정에서 마지막에 stack을 비워주면서 Sum을 구하는게 아닌, 입력의 과정에서 동시에 Sum을 계산했다. 이로 인해 마지막에 전체적인 반복을 한 번 더 하지 않아서 미세하게 더 빠르다고 볼 수 있다. 이는 정수가 0일 경우에 지울 수 있는 수가 있음이 보장된다는 전제 조건이 문제에 있기 때문에 가능한 최적화이다.

반복문 하나 밖에 없으므로, 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <stack>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iK{};
    cin >> iK;

    int iSum{};
    stack<int> stInput{};

    while(iK--)
    {
        int iInput{};
        cin >> iInput;

        // 입력 0이면 stack 맨 위 pop하면서 Sum에서도 뺌
        if(iInput == 0)
        {
            iSum -= stInput.top();
            stInput.pop();

            continue;
        }

        // Input을 Sum에 더하고 stack에 push
        iSum += iInput;
        stInput.push(iInput);
    }

    cout << iSum;

    return 0;
}

---

2. 추가 풀이 (동적 배열)

- 알고리즘

• Data Structure

- 설명

vector를 사용한 풀이이다.

stack이 아닌 vector를 사용한 풀이인데, 이게 가능한 이유는 stack의 역할을 vector가 모두 대체 가능하기 때문이다. top은 back으로, push는 push_back, pop은 pop_back으로 치환 가능하다. 따라서 모든 'stack' 문제는 'vector'를 사용하는 방식으로 대체 가능하다고 봐도 무방하다.

위와 똑같이 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iK{};
    cin >> iK;

    int iSum{};
    vector<int> vecInput{};
    vecInput.reserve(iK);

    while(iK--)
    {
        int iInput{};
        cin >> iInput;

        // vector의 맨 뒤 요소를 Sum에서 빼고 pop_back
        if(iInput == 0)
        {
            iSum -= vecInput.back();
            vecInput.pop_back();

            continue;
        }

        // Input을 Sum에 더하면서 vector에 push_back
        iSum += iInput;
        vecInput.push_back(iInput);
    }

    cout << iSum;

    return 0;
}

---

💭 후기

stack 문제를 stack, vector를 사용한 방식 두 가지를 사용해 보았다. 본래 문제의 의도는 stack 사용이 맞지만, 사실 전체적인 성능면에서 보았을 때는 vector 쪽이 더 유리하긴 하다. 그 이유는 다음과 같다.

• stack은 내부 구조가 deque으로 된 컨테이너 어댑터이므로 함수들이 호출을 한 번 더 거치게 된다.
• vector는 연속 메모리 구조로 캐시 친화율이 높다.
• vector는 reserve를 통해 재할당 방지가 가능한 반면, stack은 그런게 없다.

따라서 stack의 top / pop과 vector의 back / pop_back은 시간 복잡도가 O(1)로 같지만, 위와 같은 요인들로 인해 실제 성능은 조금 차이가 나게 되는 것이다.

꼭 stack을 써야 하는 경우는 'stack'을 쓴다는 '의미 전달'이 중요한 경우나 'stack'의 기능 외에는 아예 사용을 못하게 방지하는 경우이다. 그러므로 코테에서는 vector쪽을 적극적으로 사용하도록 하자!