[Algorithm/C++17] 백준 5076 Web Pages

문제

https://www.acmicpc.net/problem/5076

5076번: Web Pages

풀이 방법

주어진 html의 태그가 올바르게 열리고 닫혔는지 확인하는 문제이다. 스택을 이용해서 올바른 괄호 문자열인지 판별하는 것과 비슷하다. 다만 이 문제는 태그를 파싱해줘야 한다는 것이 차별점이다. 코드의 진행 과정은 다음과 같다.

1. 주어진 html문을 <, >를 기준으로 잘라 벡터에 push_back한다. 이때 여는 것과 닫는 것이 같이 있는 경우(<br/>)는 push_back하지 않는다.
2. 벡터를 순회하며 여는 태그일때는 스택에 push한다.
3. 닫는 태그일때는 스택이 비어있지 않을 경우 스택의 top과 이름이 일치하면 pop한다. 비어있는 경우엔 잘못된 경우이므로 valid를 false로 하고 순회를 종료한다.
4. 스택이 비어있지 않거나valid가 false면 잘못된 html코드이므로 illegal을 출력한다.
5. 그외엔 legal을 출력한다.

코드

#include <cstdio>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int main()
{
    vector<string> html;
    string s;
    while(true)
    {
    	getline(cin, s);
        if(s=="#") break;
        
        stack<string> st;
        vector<string> v;
        while(s.find('<') != string::npos)
        {
        	// 1. 태그를 벡터에 넣기
            // <tag attribute="">, </tag> 또는
            // <tag>, </tag> 
            // 형태로 넣어진다.
        	int start = s.find('<');
        	int end = s.find('>');
        	string tag = s.substr(start, end-start+1);
        	s = s.substr(end+1, s.size());
        	if(tag.find('/') != tag.size()-2)
        	{
        		// printf("tag:%s\n", tag.c_str()); // TEST
        		v.push_back(tag);
        	}
        }
        
        bool valid = true;
        for(int i=0; i<v.size(); i++)
        {
            // 2. 여는 태그일 때
        	if(v[i][1] != '/') 
            	st.push(v[i]);
            // 3. 닫는 태그일때
        	else 
        	{
        		if(!st.empty())
        		{
		    		// 여는 태그는 <tag attribute=" "> 또는 <tag>형태
		    		string s1 = st.top();
		    		int space = s1.find(' ');
		    		// 후자는 <, >를 잘라낸 것이 태그의 이름
		    		if(space == string::npos) s1 = s1.substr(1, s1.size()-2);
		    		// 전자는 띄어쓰기를 중심으로 잘라낸 앞의 것이 태그의 이름
		    		else s1 = s1.substr(1, space-1);
		    		
		    		// 닫는 태그는 </tag> 형태
		    		// </, >를 제외한 것이 태그의 이름
		    		string s2 = v[i].substr(2, v[i].size()-3);
                    
                    // 최종적으로 s1, s2는 태그 이름만 남게 된다.
                    // ex: strong, strong
                    // ex: body, body
                    // ex: a, a
		    		//printf("%s %s\n", s1.c_str(), s2.c_str()); // TEST
                    // top과 이름이 일치하면 pop한다.
		    		if(s1 == s2)
		    			st.pop();
        		}
        		else
        		{
                    // 닫는 태그인데 스택이 비어있으면 잘못된 태그
                    // valid flag를 false로 바꿈
        			valid = false;
        			break;
        		}
        	}
        }
        // 4. 스택이 비어있지 않거나 false면 illegal
        if(st.size() != 0 || !valid) printf("illegal\n");
        // 5. 그외엔 legal
        else printf("legal\n");
    }
    return 0;
}

고찰

검증 자체는 올바른 괄호 판별과 똑같아서 쉽지만 태그를 파싱해줘야 하는게 좀 어려웠던 문제이다.

substr과 find를 사용하면서 문자열이 어떻게 잘렸는지 일일이 printf로 확인해보고 풀었다.

열림과 동시에 닫히는 <br/>, 속성이 함께 있는 <a href=""></a>만 조심하면 된다.