[C++] 백준 5076번 - Web Pages

이 문제를 해결하는데는 두 달정도가 걸린 것 같다.

방학때 자료구조 배우고 개강하기 전에 stack 고급 문제들을 풀어봐야지 하고

무심코 도전했던 첫 골드 문제였는데 5번 제출하고도 틀렸었고,

백준에 질문을 올려서 뭘 잘못했는지 반례를 찾았고,

드디어 해결을 했다.

 

stack과 문자열 parsing을 활용한 문제였다.

html의 tag를 생각하면 되는 문제였는데, 다행히도 html의 태그 내의 css요소 들은 신경을 안써도 되었다.

그래서 a 태그, br 태그 들을 잘 생각해주면 되는 문제였다.

내가 틀린 부분은 처음에 </a>가 들어올 경우 legal로 출력이 되는 것이 문제였다.

이 부분을 처리해주고 제출했더니 correct가 떴다.

재미있기도 했고, 허무했던 stack 문제였다.

 

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <vector>
#include <sstream>
using namespace std;

vector<string> split(string input, char delimiter) {
	vector<string> answer;
	stringstream ss(input);
	string temp;

	while (getline(ss, temp, delimiter)) {
		answer.push_back(temp);
	}

	return answer;
}

int main() {

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

	while (true) {
		string s;
		getline(cin, s);

		if (s == "#")
			break;

		stack<string> st;
		for (int i = 0; i < s.length(); i++) {
			// tag 찾기 시작
			if (s[i] == '<') {
				int temp_start = i + 1;
				int temp_end = 0;
				while (s[i] != '>') {
					i++;
					temp_end++;
				}
				//tag의 단어만 파싱
				string tag = s.substr(temp_start, temp_end - 1);
				//tag에 공백 들어오는 경우를 처리 ex) 예제의 <br />, <a href="">같은거
				vector<string> temp_words = split(tag, ' ');

				if (temp_words.back() == "/") { //단일 태그 처리
					continue;
				}
				else if (temp_words[0][0] == '/') { //닫는 태그 처리
					if (!st.empty() && st.top() == temp_words[0].substr(1, temp_words[0].length())) {
						st.pop();
					}
					else if (st.empty()) {
						st.push(temp_words[0]);
					}
				}
				else { //여는 태그 처리
					st.push(temp_words[0]);
				}
			}
		}

		if (!st.empty()) {
			cout << "illegal" << "\n";
		}
		else {
			cout << "legal" << "\n";
		}
	}


	return 0;
}