4752번 HTML 에디터 문제를 풀어보고있다.(2)
4752 HTML 에디터
https://www.acmicpc.net/problem/4752
4752번: HTML 에디터
문제 백준이는 스마트폰용 HTML 에디터를 만들던 중 잘라내기/복사하기/붙여넣기 기능에서 막혔다. 간단해 보이는 기능이지만, 이 기능은 꽤 복잡한 기능이다. 그 이유는 선택한 구간의 서식을 유지해야 하기 때문이다. 하지만, 선택한 구간이 구간 밖의 태그에 영향을 받기 때문에 이 기능이 복잡한 기능이다. HTML 문서가 주어졌을 때, 백준이는 B부터 E까지 구간을 선택했다. 그 다음, B부터 E까지 부분 문자열이 원래 있던 곳에서의 서식과 동일한 서식으로
www.acmicpc.net
오랫만에 풀어보고있다 류의 게시글이다.
라고는 해도 이게 풀어보고있다 에서는 두 번째 게시글이다.
결론부터 말하면 해결하지 못 한 문제이다.
문제 내용은 HTML코드를 입력받아 B부터 E까지의 코드를 담고있는 태그들을 포함해서 따로 분류하는 것이다.
단순해 보이지만 <h></h>가 여러개 겹쳐있어서 골치아픈 문제였다.
B, E 가 주어지고 80줄이 넘지 않는 코드가 주어진다.
-1 -1이 입력될 때까지 계속하는 문제이다.
<--
입력 예시
0 15 Testing<b>!</b>
18 23 <big>100, <bigger>1000, <biggest>10000</biggest></bigger></big>
4 4 <b>123</b> 0 16 :-/ :-> :-) :-<-> </->
-1 -1
-->
<--
출력예시
Testing<b>!</b>
<big><bigger>1000,</bigger></big>
<b></b>
:-/ :-> :-) :-
-->
잘못된 코드는 입력되지 않는 것이 전제여서 쉽게 풀어나갈 수 있었다.
단순하게 B까지의 태그들을 검사하여 저장했고, B부터 E까지의 코드 내용중 포함된 태그들을 검사하여 저장하였다.
그리고 저장된 태그들과 내용을 차례대로 출력하고, 저장된 태그들을 역순으로 /을 붙여서 출력하였다.
그렇게 해결된 듯 하였지만, 문제가 생겼다.
3 16 <a><b><c>asdfasdasdfasdfasdf</c></b></a>
이런식으로 입력을 하면 앞쪽에 태그의 <가 안나오고 뒤에 </a>를 제외한 다른 출력이 되지 않았다.
그래서 나는 B를 기준으로 태그들이 먼저 시작하면 따로 검사하여 저장하는 코드를 구현하였다.
그렇게 어느정도 완성된 코드가 나왔는데...
#include <stdio.h>
int main()
{
int B,E,k,i,j,cnt,R,S,M;
char str[202],chk[202];
while(1) {
cnt=0;
R=0;
scanf("%d %d", &B, &E);
if(B==-1 && E==-1) break;
B++;
E++;
gets(str);
for(i=0; i<B-1; i++) {
if(str[i]=='<') {
i++;
for(; str[i-1]!='>'; i++) chk[++cnt]=str[i-1];
chk[++cnt]=str[--i];
}
}
S=B;
R=0;
for(i=1; i<=cnt; i++) printf("%c", chk[i]);
for(i=B; i<E; i++) {
if(str[i]=='<') {
if(str[i+1]=='/') {
cnt--;
for(j=cnt; chk[j]!='<'; j--) cnt--;
}
else {
if(i==S) {
M=1;
printf("%c", str[i]);
chk[++cnt]=str[i++];
}
for(; str[i-1]!='>'; i++) {
printf("%c", str[i]);
chk[++cnt]=str[i];
}
i--;
if(M) S=i+1;
R=0;
}
}
else {M=0;R=1;}
if(B==E || (i==B && str[i]=='>') || !R) continue;
printf("%c", str[i]);
}
for(i=cnt; i>0; i--) {
if(chk[i]=='>') {
k=i;
while(chk[i]!='<') i--;
for(j=i; j<=k; j++) {
if(chk[j-1]=='<' && chk[j]!='/') printf("/");
if(chk[j]!='>') printf("%c", chk[j]);
}
if(chk[k]=='>' && chk[k-1]!='>') printf(">");
}
}
puts("");
}
return 0;
}
문제가 생겼다.
5 16 <a>N ><b><c>f>asdfasss</c>s</b>ads</a>
를 입력했더니 <a> 를 제외하고 무한반복에 빠져버리는 끔찍한 상황이다.
현재까지는 이렇게 막혀버렸다.
3시간을 진득히들여서 고민하고 삽질했는데 못풀어서 굉장히 아쉽게 느낀다.
나중에 이어서 풀어보도록 하자.
2회차 도전이다.
사실상 코드를 전부 뜯어고쳤다.
그 이전에 당시에 왜 저렇게 코딩을 했었는지 의문이다.
그래서 이번에 구현한 방법은 stack에 각 태그들을 담아보기로 했다.
쉽게 구현되었고, 예제들도 전부 구현이 된다.
근데 반례를 모르겠다.
사실 이건 내가 어떻게 해결하기에는 머리가 멈춰버렸다.
반례에 관한 도움이 시급하다.
//살려줘
#include <stdio.h>
int B,E,i,j,top,x,n[100],s;
char str[200],chk[100][200];
void push() {
top++;
x=0;
for(;i<=j; i++,x++) chk[top][x]=str[i];
n[top]=x;
chk[top][x]='\0';
}
void pop() {
s=1;
while(s) {
if(chk[top][0]!='<') top--;
else {
printf("</");
i++;
for(x=1; x<=n[top]; x++,i++) printf("%c",chk[top][x]);
s=0;
top--;
}
}
}
int main()
{
while(1) {
top=-1;
s=0;
scanf("%d %d", &B, &E);
if(B==-1 && E==-1) break;
gets(str);
for(i=0; i<=B; i++) {
if(str[i]=='<') {
for(j=i; str[j]!='>'; j++) {}
push();
}
}
for(i=0; i<=top; i++) printf("%s", chk[i]);
for(i=B+1; i<=E; i++) {
if(str[i]=='<' && str[i+1]!='/') {
s=i;
for(j=i; str[j]!='>'; j++) {}
push();
i=s;
}
if(str[i]=='<' && str[i+1]=='/') {
pop();
if(i>=E) continue;
}
printf("%c", str[i]);
}
for(i=top; i>=0; i--) {
printf("</");
for(j=1; j<n[i]; j++) printf("%c", chk[i][j]);
}
puts("");
}
return 0;
}