STL 시퀸스 컨테이너 to 컨테이너 어답터(백준)
Published:
타 container 자료구조 구현 문제는 담에 하도록하고… 다 구현 되어있으니. stl container를 조사하면서 sequence container의 기능을 제한시켜 continer adapter를 구현한다하여, 백준문제를 해결할겸 직접 해보기로 하였다.
스택 구현
코드
#include <vector>
#include <iostream>
#include <sstream>
int main(){
int size;
std::cin >> size;
std::vector<int> v(0);
std::ostringstream oss;
for (int i = 0; i< size ; i++){
int command;
std::cin >> command;
if(command == 1){
int insert;
std::cin >> insert;
v.push_back(insert);
} else if(command == 2){
if(v.size() <= 0){
oss << -1<< '\n';
}
else{
oss << v.at(v.size()-1)<<'\n';
v.pop_back();
}
} else if(command == 3) {
oss << v.size()<< '\n';
} else if (command == 4) {
if(v.size() == 0)
oss << 1<< '\n';
else
oss << 0<< '\n';
} else {
if(v.size() <= 0)
oss << -1<< '\n';
else
oss << v.at(v.size()-1)<<'\n';
}
}
std::cout<< oss.str() << std::flush;
return 0;
}
양 끝단에서의 삽입, 삭제가 가장 빠른 벡터를 이용하였다. 구현자체가 어렵지 않아 큰 문제는 없었다. 왜 벡터로 구현하지 같은 의문점은 stl container 관련해 정리하며 그 게시물에 정리해 두었다.
큐 구현
구현
#include <deque>
#include <iostream>
#include <sstream>
#include <string>
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
std::ostringstream alls;
int command;
std::cin >> command;
std::cin.ignore();
std::deque<int> q(0);
for(int i = 0; i< command; i++){
std::string onelinecommand;
std::getline(std::cin, onelinecommand);
std::stringstream onelinecommandstream(onelinecommand);
std::string first;
std::getline(onelinecommandstream, first, ' ');
std::string second;
if (first == "push"){
std::getline(onelinecommandstream,second);
q.push_front(std::stoi(second));
} else if (first == "pop") {
if(q.size() <= 0){
alls <<"-1\n";
continue;
}
alls << q.back() << '\n';
q.pop_back();
} else if (first == "size") {
alls << q.size() << '\n';
} else if (first == "front") {
if(q.size() == 0)
alls << "-1\n";
else
alls << q.back() << '\n';
} else if (first == "empty") {
if(q.size() == 0)
alls << "1\n";
else
alls << "0\n";
} else if (first == "back") {
if(q.size() == 0)
alls << "-1\n";
else
alls << q.front() << '\n';
}
}
std::cout << alls.str() << std::flush;
}
큐 역시 양 끝단으로만 접근한다 생각하여 최초는 vector로 구현하였다. 그러나 vector가 우측 끝단의 삽입만 허용하는 걸 몰랐었다. 그래서 하나하나 다시 deque로 바꿨다… 구현시에 내가 활용하는 라이브러리가 특정 기능을 지원하는지 여부를 살피는 것도 중요한것 같다.
백준에서 runtimeerror 발생 이유를 살피지 않아서 오래 걸렸다… 다음에는 꼭 살펴보자.
다른 사람 코드 참고하기
나중에 추가…