[백준/Day 1] - 스택2 (vector로 stack 구현)

1. 문제 재정의

5가지 명령을 처리하는 정수를 저장하는 스택을 구현해야 한다.

• 정수 X를 스택에 넣는다: void push(int X);
• 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다: void pop();
• 스택에 들어있는 정수의 개수를 출력한다: void size();
• 스택이 비어있으면 1, 아니면 0을 출력한다: void isEmpty();
• 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다: void printTop();

처음에는 명령의 수 N을 받는데, 입력이 1이상 100만 이하이므로
시간 복잡도는 O(NlogN), O(N), O(logN) 중 하나의 자료구조, 알고리즘을 선택해야 한다.
→ 맨 위에 정수를 넣고, 빼는 동작을 한다.
vector STL은 맨끝의 삽입·삭제에 O(1)의 시간 복잡도를 갖기 때문에 이로 구현한다.

2. 문제 해결 과정

#include <iostream>
#include <vector>

class Stack {
  public:
    Stack() {}
    ~Stack() 
    {
        delete[] stack;
    }

    void push(int X)
    {
        stack.push_back(X);
    }
    int pop()
    {
        int top = stack.top();
        top != -1 && stack.pop_back();

        return top;
    }
    bool isEmpty()
    {
        return stack.size() == 0 ? 1 : 0;
    }
    int top()
    {
       return stack.size() > 0 ? stack.back() : -1; 
    }

  private:
    std::vector<int> stack;
};


int main() {
    Stack stack = new Stack();

    int commandLine;
    std::cin >> commandLine;

    for (int i = 0; i < commandLine; ++i)
    {
        std::string command;
        std::getline(std::cin, command);

        switch (command[0])
        {
            case 1:
                stack.push(command[2]);
                break;
            case 2:
                std::cout << stack.pop() << "\n";
                break;
            case 3:
                std::cout << stack.size() << "\n";
                break;
            case 4:
                std::cout << stack.isEmpty() << "\n";
                break;
            case 5:
                std::cout << stack.top() << "\n";
                break;
            default:
                std::cout << -1 << "\n";
                break;
        }
    }

    return 0;
}

• error: type class std::vector<int> argument given to delete , expected pointer
  • delete[] stack; → delete stack;
• error: class std::vector<int> has no member named top
  • top 함수 위치 위로 조정
• error: could not convert ((Stack*)this)->Stack::stack.std::vector<int>::pop_back() from void to bool
  • stack.pop_back()은 반환형이 void이기에, && 연산자에 이어서 사용할 수 없다.
• error: conversion from Stack* to non-scalar type Stack requested
  • new 키워드로 생성한 객체는 주소를 반환하기 때문에 *을 붙여줘야 한다.
• error: class Stack has no member named size
  • vector STL에는 size 함수가 있지만, 생성한 클래스에는 size 함수가 없기 때문에 만들어 줘야 한다.

#include <iostream>
#include <vector>

class Stack {
  public:
    Stack() {}
    ~Stack() 
    {
        delete stack;
    }

    int top()
    {
       return stack.size() > 0 ? stack.back() : -1; 
    }

    void push(int X)
    {
        stack.push_back(X);
    }

    int pop()
    {
        int top = stack.top();
        if (top != -1) stack.pop_back();

        return top;
    }

    bool isEmpty()
    {
        return stack.size() == 0 ? 1 : 0;
    }

    int size()
    {
        return stack.size();
    }


  private:
    std::vector<int> stack;
};


int main() {
    Stack* stack = new Stack();

    int commandLine;
    std::cin >> commandLine;

    for (int i = 0; i < commandLine; ++i)
    {
        std::string command;
        std::getline(std::cin, command);

        switch (command[0])
        {
            case 1:
                stack.push(command[2]);
                break;
            case 2:
                std::cout << stack.pop() << "\n";
                break;
            case 3:
                std::cout << stack.size() << "\n";
                break;
            case 4:
                std::cout << stack.isEmpty() << "\n";
                break;
            case 5:
                std::cout << stack.top() << "\n";
                break;
            default:
                std::cout << -1 << "\n";
                break;
        }
    }


    return 0;
}

• error: type class std::vector<int> argument given to delete, expected pointer
  • vector는 자동으로 메모리 해제된다. (RAII)
• error: request for member push in stack, which is of pointer type Stack* (maybe you meant to use -> ?)
  • new 키워드로 생성했을 때 *을 붙였으므로 멤버 함수에 접근할 때 -> 연산자를 사용해야 한다.
• error: class std::vector<int> has no member named top
  • stack은 vector를 가리키고 있기 때문에 top() 함수가 없다. 멤버 함수 top()을 쓰려면 this->top()로 작성 해야 한다.

#include <iostream>
#include <string>
#include <vector>

class Stack {
  public:
    Stack() {}
    ~Stack() = default;

    int top()
    {
       return stack.size() > 0 ? stack.back() : -1; 
    }

    void push(int X)
    {
        stack.push_back(X);
    }

    int pop()
    {
        int top = this->top();
        if (top != -1) stack.pop_back();

        return top;
    }

    bool isEmpty()
    {
        return stack.size() == 0 ? 1 : 0;
    }

    int size()
    {
        return stack.size();
    }


  private:
    std::vector<int> stack;
};


int main() {
    Stack* stack = new Stack();

    int commandLine;
    std::cin >> commandLine;

    for (int i = 0; i < commandLine; ++i)
    {
        std::string command;
        std::getline(std::cin, command);

        switch (command[0])
        {
            case 1:
                stack->push(command[2]);
                break;
            case 2:
                std::cout << stack->pop() << "\n";
                break;
            case 3:
                std::cout << stack->size() << "\n";
                break;
            case 4:
                std::cout << stack->isEmpty() << "\n";
                break;
            case 5:
                std::cout << stack->top() << "\n";
                break;
            default:
                std::cout << -1 << "\n";
                break;
        }
    }

    return 0;
}

• 실행 안해보고 풀어보려하다가 출력초과가 떠서 왜이러는지 찾아보기로 했다.
• getline이 첫 줄을 빈 문자열로 읽기 때문에 cin으로 받는 게 낫다고 한다.
• 또, new 키워드로 객체를 생성할 필요 없다고 한다.

#include <iostream>
#include <string>
#include <vector>

class Stack {
public:
    Stack() {}
    ~Stack() = default;

    int top()
    {
        return stack.empty() ? -1 : stack.back();
    }

    void push(int x)
    {
        stack.push_back(x);
    }

    int pop()
    {
        if (stack.empty()) return -1;
        int v = stack.back();
        stack.pop_back();

        return v;
    }

    bool isEmpty() const
    {
        return stack.empty();
    }

    int size() const
    {
        return stack.size();
    }


private:
    std::vector<int> stack;
};


int main() {
    Stack stack;

    int N;
    std::cin >> N;

    while (N--)
    {
        int cmd;
        std::cin >> cmd;

        switch (cmd)
        {
        case 1:
            int x;
            std::cin >> x;
            stack.push(x);
            break;
        case 2:
            std::cout << stack.pop() << "\n";
            break;
        case 3:
            std::cout << stack.size() << "\n";
            break;
        case 4:
            std::cout << stack.isEmpty() << "\n";
            break;
        case 5:
            std::cout << stack.top() << "\n";
            break;
        default:
            std::cout << -1 << "\n";
            break;
        }
    }

    return 0;
}

• 하하, 이제 출력 초과는 안뜨는데 시간 초과가 뜬다. 요구사항 다 감안해서 했는데 왜 시간 초과가 뜨지?
• 아래 두줄을 추가했더니 시간 초과가 안뜨고 맞았습니다가 뜬다..
• std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

#include <iostream>
#include <string>
#include <vector>

class Stack {
public:
    Stack() {}
    ~Stack() = default;

    int top()
    {
        return stack.empty() ? -1 : stack.back();
    }

    void push(int x)
    {
        stack.push_back(x);
    }

    int pop()
    {
        if (stack.empty()) return -1;
        int v = stack.back();
        stack.pop_back();

        return v;
    }

    bool isEmpty() const
    {
        return stack.empty();
    }

    int size() const
    {
        return stack.size();
    }


private:
    std::vector<int> stack;
};


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

    Stack stack;

    int N;
    std::cin >> N;

    while (N--)
    {
        int cmd;
        std::cin >> cmd;

        switch (cmd)
        {
        case 1:
            int x;
            std::cin >> x;
            stack.push(x);
            break;
        case 2:
            std::cout << stack.pop() << "\n";
            break;
        case 3:
            std::cout << stack.size() << "\n";
            break;
        case 4:
            std::cout << stack.isEmpty() << "\n";
            break;
        case 5:
            std::cout << stack.top() << "\n";
            break;
        default:
            std::cout << -1 << "\n";
            break;
        }
    }

    return 0;
}

3. 인사이트

1) 소유권 규칙: new/delete는 “직접 소유”할 때만

• std::vector 같은 표준 컨테이너는 스스로 메모리를 관리(RAII) 한다.
• 그래서 클래스 멤버로 vector를 두면 소멸자에서 delete를 절대 하지 않는다.
• new로 객체 만들었으면 반드시 delete가 짝인데, 문제풀이에선 애초에 new가 필요 없다.

습관:

“표준 라이브러리 타입이면 delete 금지”
“문제풀이 객체는 지역변수로 생성”

---

2) “멤버 함수 소속”을 항상 구분하기

너가 만든 Stack::top() 과 vector::back()이 섞였던 게 핵심이었지.

• stack.top() → 여기서 stack이 vector면 top() 없음
• 클래스의 top을 쓰려면 top() 또는 this->top()

습관:

변수명이 stack이어도 타입이 vector면 back/pop_back만 된다.
“이 함수는 누구의 멤버인가?”를 먼저 확인

---

3) 연산자 트릭은 “반환형”을 먼저 본다

cond && func() 패턴은 func가 bool로 평가 가능한 값을 반환해야 한다.

• pop_back()은 void → && 오른쪽에 못 옴

습관:

한 줄 트릭 쓰기 전에 “반환형이 void인가?”부터 확인
조건부 실행은 if가 가장 안전

---

4) 입력 처리: getline과 >> 혼용은 위험

cin >> N 뒤에 바로 getline 하면 첫 줄이 빈 문자열이 된다(개행이 남아있어서).
그리고 백준은 대부분 토큰 기반이라 getline + stoi는 불리하다.

습관:

• 명령이 정수/토큰이면 끝까지 cin >>로만 간다.
• 혼용이 필요하면 ignore()를 먼저 한다.

---

5) switch 안에서 변수 선언은 블록으로 감싸라

case 1: int x = ...; 는 “jump to case label” 이슈가 나기 쉽다.

습관:

case 1: {
    int x; cin >> x;
    ...
    break;
}

---

6) 성능 관점 핵심: “알고리즘” 말고 “I/O 상수”가 병목일 수 있다

네가 시간 초과를 해결한 결정타가 이거였지:

ios::sync_with_stdio(false);
cin.tie(nullptr);

N이 100만이면 스택 연산은 O(N)으로 충분해도,
입출력 비용이 전체를 잡아먹는다.

습관(백준 기본 템플릿화):

• 항상 위 2줄을 기본으로 깔기
• 출력이 많으면 문자열 누적 후 한 번에 출력도 고려

---

7) “출력 초과/시간 초과/런타임 에러”를 원인별로 즉시 분류

• 출력 초과: 루프 조건/입력 파싱 오류(빈 줄, switch 분기, default 남발) 의심
• 런타임 에러: command[0] 같은 범위 밖 접근, empty에서 back/pop, delete 오용 의심
• 시간 초과: getline+stoi, 동기화 미해제, flush/endl 남발, 불필요한 동적할당 의심

---

한 줄로 정리

C++ 문제풀이는 “자료구조 선택”보다 RAII(소유권), 타입(멤버 소속), 입력 방식, I/O 최적화를 기본 습관으로 깔아두는 게 실수를 줄인다.