[스택] 정올 1015번 브라우저

출처 : East Central North America 2001, poj 1028

 

톡방에서 추천 받은 스택 문제인데 구글에 풀이가 바로 안나오길래 올려놓습니다.

 

문제

 

초기 웹 페이지는 acm.org 로 설정된 상태에서 주어진 명령에 따라 웹페이지 및 스택이 변화한다.

우선 스택은 크게 두 종류가 있는데 페이지를 "앞으로 이동하게" 도와주는 forward Stack,

페이지를 "뒤로 가게" 도와주는 backward Stack이 있다.

 

문제에서 나오는 명령어는 4가지로, BACK, FORWARD, VISIT, QUIT가 있고 각각의 역할은 다음과 같다.

 

• BACK : 현재 페이지를 forward Stack에 push하고, backward Stack을 pop해 현재 페이지로 만든다.
• FORWARD : 현재 페이지를 backward Stack에 push하고, forward Stack을 pop해 현재 페이지로 만든다.
• VISIT : 현재 페이지를 backward Stack에 push 하고, forward Stack을 모두 비운다.
• QUIT : 작업을 그만 둔다.

다음과 같은 명령들이 주어질 때마다, 현재 페이지를 출력하라.

 

 

풀이

 

문제 풀 때 저는 이런식으로 문제를 분석하고 푸는 편인데, 참고가 될 지 모르겠네요 ㅎㅎ..

이 문제는 스택을 이용하긴 하나, 문제에 주어진 대로 그대로 코드에 옮기면 되는 스택 + 구현 문제 같아요.

아마 모두 쉽게 푸실 것 같지만, 유의할 점은 비어있을 때 예외처리와, 스택을 비울 때 어떻게 코드를 짜는지만 보시면 될 것 같습니다.

 

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	string url = "http://www.acm.org/";
	stack<string>s, e; //foward, backward

	while (1)
	{
		string cmd;
		cin >> cmd;
		if (cmd == "QUIT") break;
		else if (cmd == "BACK") {
			if (e.empty()) {
				cout << "Ignored" << "\n";
				continue;
			}
			s.push(url);
			url = e.top();
			e.pop();
		}
		else if (cmd == "FORWARD") {
			if (s.empty()) {
				cout << "Ignored" << "\n";
				continue;
			}
			e.push(url);
			url = s.top();
			s.pop();
		}
		else if (cmd == "VISIT") {
			string tmp; cin >> tmp;
			e.push(url);
			url = tmp;
			while (!s.empty()) s.pop();
		}
		cout << url << "\n";
	}

	return 0;
}