- 문제 링크
백준 10828번 - 스택
해결 전략
사실, 이 문제는 정말 쉬운 문제이고, 사실상 취업 시의 코딩 테스트엔 이런 수준의 문제는 출제되지 않을 가능성이 높다. 그럼에도 불구하고 본인이 이 문제를 포스팅하는 것은, 초심자 프로그래머들에게, 본인 역시 아직 고수는 결코 아니지만 그럼에도 명문 컴퓨터공학과 학부 자료구조 수업에서 최고 수준 성적을 받았던 사람으로서 조언을 주자면, '직접 자료 구조를 구현하는 능력'이 매우 중요하다는 것을 전달하고 싶어서 포스팅한다.
C++의 STL과 같은, 언어에서 제공하는 고급 라이브러리를 적극 사용하는 것은 당연히 좋은 것이고, 권장되는 것이지만, 그 행위에 있어서 한 가지 반드시 지켜야할 전제 조건이 있다.
라이브러리에 구현된 자료구조를 본인 힘으로 직접 구현할 수 있어야 한다. 그런 능력이 있는 자만이 STL을 자유롭게 쓸 자격이 있다.
그리고, 여기서 본인이 이야기하는 '자료구조 구현 능력'이란, Linked List를 필두로 한 스택, 큐, 덱, 벡터 등의 구조와, 트리, 특히나 이진 트리 등을 의미한다. 그 이상의 고급 자료 구조는 사실상 PS 상황에서 직접 구현하기가 쉽지 않기 때문에 논외로 한다(물론, 충분한 시간이 제공된다면 누구나 구현할 수 있다. 예를 들어 B트리).
여기서 가장 중요한 것은, 'Linked List'를 구현할 줄 아느냐이다. Linked 개념이 바로 상기한 기본 자료구조들의 근간이기 때문이다.
'Linked' 개념에 대한 깊이 있는 이해가 바로 '기본 자료구조 구현 능력'의 핵심이다.
본인이 여기서 세세한 자료구조 구현 스킬을 설명할 이유는 없다고 생각한다. 매우 잘 정리된 서적이 시중에 너무나 많기 때문이다. 학부 전공 서적도 좋고, 시중 도서로는 아무래도 '윤성우 씨'의 열혈 C프로그래밍과 열혈 자료구조 책이 가독성도 좋고 무난하다. 어떤 도서를 택하든, 한 가지의 '좋은 도서'를 고른 후, 본인 힘으로 자료구조를 구현할 줄 아는 능력을 반드시 익히도록 하자. 나 역시도 꾸준히 복습하면서 자료구조 구현력을 유지하도록 하겠다.
아래는 본 문제에 대한 정답 코드이다. 일부러 STL 사용 없이 완전히 Naive하게 Stack을 구축하였다.
#include <iostream>
#include <string>
// BOJ - 10828 Stack
using namespace std;
typedef struct _node {
int key;
struct _node *link;
}Node;
Node *head = NULL;
int stackCnt;
bool sEmpty(void) { if (stackCnt == 0) return true; return false; }
void sTop(void) {
if (sEmpty()) { cout << -1 << '\n';; return; }
cout << head->key << '\n';
}
void sPush(int x) {
Node *newNode = new Node;
newNode->key = x;
newNode->link = head;
head = newNode;
stackCnt++;
}
void sPop(void) {
if (sEmpty()) { cout << -1 << '\n';; return; }
Node *delNode = head;
head = head->link;
cout << delNode->key << '\n';
delete[] delNode;
stackCnt--;
}
void sSize(void) { cout << stackCnt << '\n'; }
int main(void) {
int n, num; string option;
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> option;
switch (option[0]) {
case 'p': if (option[1] == 'u') { cin >> num; sPush(num); }
else sPop(); break;
case 't': sTop(); break;
case 's': sSize(); break;
case 'e': cout << sEmpty() << '\n'; break;
}
}
return 0;
}