문제 이해 단계
https://www.acmicpc.net/problem/22859
상당히 문제가 길고 조건이 많은 문제라
필요한 조건만 밑에 적어보자.
HTML 문법 형식으로
줄 바꿈 없이 한 줄로 입력이 들어온다.
핵심이 되는 태그는 <main> <div> <p>이다.
1. 모든 태그와 문자열은 <main> ~ </main> 사이에서 벌어져야 한다.
2. <div title = "(A)" 형식으로 무조건 title = "(A)"이 입력으로 들어오고
여기서 A는 여러 문단 뭉텅이의 제목이 된다.
3. <p>~</p> 사이에 있는 문자열은 좌우의 공백은 없애고
중간에 두 번 이상 띄어쓰기 되어있으면 한 번으로 줄인다.
그리고 출력 형식은 예제와 같다.
더 중요한 것은 입력이 이런 식으로 무조건 주어진다고 보장한다는 것인데,
1. 제목의 시작과 끝 부분에는 공백이 없다.
2. <p> ~ </p> 태그 사이에는
다른 태그도 존재 가능
3. 태그를 표현하는 <> 제외하고는
알파벳과 공백, ' / ' (닫는 태그에만)만 쓰인다.
4. <p> ~ </p> 안에 있는 태그 제외하고서는
나머지 < ~ > 안에 공백은 존재하지 않는다.
그러니까 <d i v> 이런 식으로 주어지진 않는다는 소리이다.
해당 조건이 주어질 때, 해
당 출력 형식으로 정확히 출력하는 문제이다.
문제 접근 단계
이 문제는 딱 봐도 구현문제다.
그냥 대놓고 구현해 볼 테 면 해봐라 이런 식인 것 같다.
구현해야 할 부분이 많을 것 같아서 함수를 잘 나눠서 설정해둬야 할 것 같다.
일단 필요한 기능을 살펴보자.
최우선적으로
(1)
들어온 문자열을 일정한 단위로 잘라
태그와 일반 문자열을 구분해야 한다.
<p> adfd </p>이면 <p>와
adfd와 </p>는 서로 다르기 때문에
구분돼야 하듯이 말이다.
그렇게 일정한 단위로 잘랐다면 이게
(2)
시작 태그인지, 종료 태그인지,
일반 문자열인지 파악해야 한다.
태그 중 <div> 태그에는 title이 있는데 이것도 출력해줘야 한다.
출력해줘야 하는 것은 " " 안에 있는 것,
즉,
(3)
<div> 태그에 있는 title도 추출해야 한다.
근데 이걸 또 그대로 출력해도 되나? 그렇지 않다.
(4)
좌우 공백은 제거해 주고 중간에 띄어쓰기가
2번 이상은 것은 1번으로 바꿔줘야 한다.
그리고 출력할 때의 사항을 보면
(5)
div 별로 제목이 나와야 하고
<p> 별로 줄 바꿈 하면서 출력해야 한다.
또한
(6)
<p>~</p> 태그 안에 있는 나머지 태그는 출력하지 않는다.
이건 추가적인 사항일 수도 있지만 출력할 때
문자들의 순서가 바뀌지 않도록 주의해야 한다.
복잡한 구현문제의 경우 구현해야 할 것을
미리 정리해 놓고 문제 풀이에 들어가는 게 나은 것 같다.
구현문제인 만큼 문제 구현 단계에서
코드를 풀이하면서 정리하겠다.
문제 구현 단계
1. 기본 로직 설명
stack<char> s; // 한 문자씩 담을 스택
stack<string> codes; // 완성된 단어를 담을 스택
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
string html;
getline(cin,html);
// 한 문자씩 탐색
for(int i = 0; i < html.length(); i++){
string str = "";
switch(html[i]){
case '<' :
if(!s.empty()) {
str = makeWord(); // 단어 만들기
classifyWord(str); // 단어 분류
str.clear(); // 초기화
}
s.push(html[i]); // 문자 넣기
break;
case '>' :
// 문자 넣고 단어를 만듦
s.push(html[i]);
str = makeWord();
classifyWord(str);
str.clear();
break;
// 알파벳이나 공백일 경우 그냥 넣음
default:
s.push(html[i]);
}
}
}2개의 스택을 사용한다.
스택 s는 char형 문자를 담는 것이고,
스택 codes는 문자열을 담는 스택이다.
기본적인 로직은 전체 입력을 처음부터 한 문자씩 탐색한다.
한문자씩 읽으면서 그 단어를 스택 s에 넣는다.
일정 조건이 만족되면,
s에 담겨있던 모든 값으로 한 문자열을 만들어
그 문자열을 스택 codes에 push 한다.
만들어진 문자열은 위에서 조건에 의해 여러 함수에 사용된다.
일단 이것이 기본 로직이다.
2. 구분하여 문자열 만들기
일단 해당 html 문법에서 >가 오면 태그가 닫힘을 의미하므
로 하나의 문자열이 끝남을 의미한다.
<main> , <div ~~~ >, <p> , <br > 등 전부 >로 끝나기 때문.
그리고 <가 오면 일단 <를 넣어주기 전에
이전까지의 값을 문자열을 만들어줘야 한다.
왜냐하면 이전에 계산해 둔 값이 존재할 수 있기 때문이다. (예 : "adsfasdf <")
그럼 어떻게 문자열을 구성할까, 다음 함수를 사용한다.
// 단어 만들기
string makeWord(){
string tmp = "";
while(!s.empty()){
tmp.insert(tmp.begin(),s.top());
s.pop();
}
return tmp;
}
간단하게 스택 s에 있는 값을 모두 빼서 만들어주면 된다.
여기서 유의 깊게 봐야 하는 것은
빼준 요소 하나하나를 맨 앞에 두는 것이다.
이렇게 하는 이유는 스택에 나온 순서대로 출력하면
반전돼서 나오기 때문에,
늦게 나온 값을 앞으로 놔두는 것으로
올바른 값이 나오게 하는 것이다.
3. 중간 중복 띄어쓰기 제거
// 다중 띄어쓰기 제거
string removeEmpty(string word){
if(word.empty() || word.length() <= 1) return word;
string str = "";
int combo = 0;
for(int i = 0; i < word.length(); i++){
if(word[i] == ' ') combo++;
else combo = 0;
if(combo < 2) {
str.push_back(word[i]);
}
}
return str;
}
문제 조건 중에 <p> ~ </p> 안에 있는 것 중에
띄어쓰기가 2개 이상인 것은 하나로 만들어주라고 했다.
여기서는 combo라는 변수를 이용해서 이를 판단한다.
띄어쓰기가 발견되면 combo + 1,
띄어쓰기가 아니면 combo = 0으로 하여
띄어쓰기가 연속해서 나와야 2,3,4로 갈 수 있게 해 놨다.
그렇게 combo가 2 미만일 때만
재구성할 문자열에 다시 넣어준다.
// 좌우 공백 제거
string trim(string word){
if(word.length() <= 1) return word;
if(word[0] == '<'){
// 시작+1 공백 제거
while(word[1] == ' ') word.erase(word.begin()+1);
// 끝-1 공백 제거
while(word[word.size()-2] == ' ')
word.erase(word.begin()+word.size()-2);
}
else{
// 시작 공백 제거
while(word[0] == ' ') word.erase(word.begin());
// 끝 공백 제거
while(word[word.size()-1] == ' ')
word.erase(word.begin()+word.size()-1);
}
return word;
}
<p> ~ </p> 태그 사이에서 좌우 공백을 제거하는 함수이다.
C++에서는 trim함수가 없기 때문에 직접 구현해줘야 한다.
방법은 매개변수 word가 태그인지 아닌지에 따라 나뉘는데
사실 로직은 같고 인덱스 위치만 다르다.
태그이면 <가 붙기 때문에 문자는 인덱스 1부터 시작하기 때문이다.
문자가 시작하는 인덱스가
공백이 아닐 때까지 그 인덱스를 제거한다.
마찬가지로 마지막 문자가 있는 인덱스도
공백이 아닐 때까지 인덱스를 제거한다.
4. 순서대로 출력하기
// 시작 태그를 찾을 때 까지 pop하면서 출력
void popAndPrint(string endTag){
vector<string> print;
// codes 스택의 가장 위가 endTag와 같을 때까지
while(codes.top().compare(endTag) != 0){
// 그 전에 pop한 문자열은 프린트할 vector에 저장
string str = codes.top();
codes.pop();
print.push_back(str);
}
if(!codes.empty()) codes.pop(); // 시작 태그 스택에서 제거
string output = "";
reverse(print.begin(),print.end()); // 순서를 위해 뒤집음
for(auto it : print) output.append(it); // 문자열로 붙임
// 공백 제거
output = removeEmpty(output);
output = trim(output);
cout << output << "\n";
}
이 함수는 매개변수는 endTag는
여기에 들어오기 이전에 '/'를 제거하여 시작태그와 똑같이 만들어놨다.
즉 </main>에서 /를 제거해서 <main>으로 만들어놨다는 뜻이다.
이는 밑에서 시작태그를 찾기 위해서이다.
이렇게 시작 태그를 찾을 때까지 pop을 하면서
그 안에 있는 문자열을 모두 담는다.
그리고 이를 한번 반전시키는데,
이는 아까도 말했듯이 스택에서 빼낸 거라
값이 반전되어 있기 때문이다.
결과 벡터를 모두 한 문자열로 이어 붙여주고
최종적으로 trim과 removeEmpty로
좌우공백과 가운데 공백을 제거해 준다.
5. 단어 구분 및 전체 제어
// 단어를 판단하고, 출력 담당하는 메인
void classifyWord(string str){
if(str.empty()) return;
//태그 옵션일 때
if(str[0] == '<'){
// 시작 태그일 때
if(str.find('/') == string::npos){
// <main>이나 <p>태그 일때만 codes에 넣음
if(str.compare("<main>") == 0 || str.compare("<p>") == 0) codes.push(str);
// div 태그를 찾음
else if(str.find("<div title=") != string::npos){
if(str.find('"') != string::npos){
getTitle(str); // 타이틀 출력
}
}
}
// 종료 태그일 때
else{
int idx = str.find('/');
// '/' 문자 제거 후에 popAndPrint 호출
str.erase(str.begin()+idx);
if(str.compare("<main>") == 0 || str.compare("<p>") == 0){
popAndPrint(str);
}
}
}
// 그냥 문자열 일 때
else codes.push(str);
}
마지막으로 들어온 단어가 그냥 문자열인지 태그인지 구분하고,
또 그게 어떤 태그인지 구분하는 함수이다.
이 함수가 핵심함수인 이유는
이 함수에서 다른 모든 함수를 거의 호출하기 때문이다.
위에서부터 설명하면 '<'로 시작한다는 것은 시작태그를 의미하는데,
그 안에서도 <main>과 <p> 일 때만 넣는 이유는
<p>~</p> 안에 있는 다른 태그들은 자연스럽게 출력해주지 않기 위해
애초에 넣어주질 않는 것이다.
그리고 div는 따로 구분하였는데
이는 find를 사용하여 해당 문자열을 포함하고 있는지를 했다.
만약 "<div" 이런 식으로 했다면 "<diving>" 이런 태그도 입력될 수 있기 때문에
최대한 형식대로 자세히 적어줬다.
종료태그일 때는 아까 말했듯이
'/'를 제거해 준 문자열로 popAndPrint를 호출한다.
이게 모든 코드에 대한 설명이다.
이제 아래에 전체 코드에 대해 올리고 설명을 마치겠다.
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
stack<char> s; // 한 문자씩 담을 스택
stack<string> codes; // 완성된 단어를 담을 스택
string cntTitle = "";
// 이중 띄어쓰기 제거
string removeEmpty(string word){
if(word.empty() || word.length() <= 1) return word;
string str = "";
int combo = 0;
for(int i = 0; i < word.length(); i++){
if(word[i] == ' ') combo++;
else combo = 0;
if(combo < 2) {
str.push_back(word[i]);
}
}
return str;
}
// 좌우 공백 제거
string trim(string word){
if(word.length() <= 1) return word;
if(word[0] == '<'){
// 시작+1 공백 제거
while(word[1] == ' ') word.erase(word.begin()+1);
// 끝-1 공백 제거
while(word[word.size()-2] == ' ')
word.erase(word.begin()+word.size()-2);
}
else{
// 시작 공백 제거
while(word[0] == ' ') word.erase(word.begin());
// 끝 공백 제거
while(word[word.size()-1] == ' ')
word.erase(word.begin()+word.size()-1);
}
return word;
}
// 단어 만들기
string makeWord(){
string tmp = "";
while(!s.empty()){
tmp.insert(tmp.begin(),s.top());
s.pop();
}
return tmp;
}
// <div> 태그에서 " " 안에 있는 이름 추출
void getTitle(string word){
string title = "";
int idx = word.find('"');
while(word[++idx] != '"') title += word[idx];
cout << "title : " << title << "\n";
}
// 시작 태그를 찾을 때 까지 pop하면서 출력
void popAndPrint(string endTag){
vector<string> print;
// codes 스택의 가장 위가 endTag와 같을 때까지
while(codes.top().compare(endTag) != 0){
// 그 전에 pop한 문자열은 프린트할 vector에 저장
string str = codes.top();
codes.pop();
print.push_back(str);
}
if(!codes.empty()) codes.pop(); // 시작 태그 스택에서 제거
string output = "";
reverse(print.begin(),print.end()); // 순서를 위해 뒤집음
for(auto it : print) output.append(it); // 문자열로 붙임
// 공백 제거
output = removeEmpty(output);
output = trim(output);
cout << output << "\n";
}
// 단어를 판단하고, 출력 담당하는 메인
void classifyWord(string str){
if(str.empty()) return;
//태그 옵션일 때
if(str[0] == '<'){
// 시작 태그일 때
if(str.find('/') == string::npos){
// <main>이나 <p>태그 일때만 codes에 넣음
if(str.compare("<main>") == 0 || str.compare("<p>") == 0) codes.push(str);
// div 태그를 찾음
else if(str.find("<div title=") != string::npos){
if(str.find('"') != string::npos){
getTitle(str); // 타이틀 출력
}
}
}
// 종료 태그일 때
else{
int idx = str.find('/');
// '/' 문자 제거 후에 popAndPrint 호출
str.erase(str.begin()+idx);
if(str.compare("<main>") == 0 || str.compare("<p>") == 0){
popAndPrint(str);
}
}
}
// 그냥 문자열 일 때
else codes.push(str);
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
string html;
getline(cin,html);
// 한 문자씩 탐색
for(int i = 0; i < html.length(); i++){
string str = "";
switch(html[i]){
case '<' :
if(!s.empty()) {
str = makeWord(); // 단어 만들기
classifyWord(str); // 단어 분류
str.clear(); // 초기화
}
s.push(html[i]); // 문자 넣기
break;
case '>' :
// 문자 넣고 단어를 만듦
s.push(html[i]);
str = makeWord();
classifyWord(str);
str.clear();
break;
// 알파벳이나 공백일 경우 그냥 넣음
default:
s.push(html[i]);
}
}
}
시행착오
푸는데 이틀 걸렸다.
포기하려고 했다가 인터넷 찾아봐도 C++로 된 풀이는 없더라.
진짜 구현문제 토 나온다.
문자열 파싱도 그래도 이 정도로 맛봤으면 어느 정도는 할 수 있겠지.
이 문제를 풀면서 덕분에 find와 compare의 차이
, 함수를 체계적으로 짜야겠다는 필요성
trim 함수가 필요하다. 뿌듯함. 여러 가지 많이 느꼈다.
구현 문제 잘 풀고 싶다. 아니 그냥 알고리즘 좀 잘하고 싶다.