알고리즘 문제 - HTML 뒤집기
시리즈 "알고리즘 문제풀기" 개요
- 1~2주 (최소) 1개 문제 풀기를 목표로 한다.
- JavaScript 로 푼다.
문제
HTML 문자열이 아래와 같이 있을 때
<p>
<b>h<font color="red">el</font>lo</b> <i>w</i>orld
</p>
아래처럼 HTML 태그들의 적용 범위는 그대로 두면 문자열을 뒤집자.
<p>
dlro<i>w</i> <b>ol<font color="red">le</font>h</b>
</p>
반드시 전문은 특정 태그로 감싸여 있다고 (위 예제에서는 p
태그로 전문이 감싸여 있다) 가정한다.
접근
처음에는 태그들을 임의의 토큰들로 치환한 다음에 문자열을 싹 뒤집고 다시 토큰들을 태그로 치환하는 방법을 생각했다. 하지만 그렇게 하기에는 토큰은 뒤집어지지 않도록 또 별도의 처리를 해줘야 했기에, 그냥 태그인 상태로 작업하는 것과 별다를 것이 없다는 결론을 내렸다. 게다가 토큰으로 변경하는 것으로는 태그가 많이 중첩될 경우 처리가 까다로웠다.
그 다음으로 생각한 건 문자열을 태그 혹은 태그가 아닌 문자열로 모두 쪼갠 뒤, 해당 문자열을 차례로 스택에 넣다가 닫는 태그를 넣을 차례가 되었을 때 바로 직전 여는 태그까지 스택에서 pop 한 뒤 뒤집는 처리를 해서 집어넣으면 어떨까 하는 것이었다.
예를 들면 문제에 나온 문자열을 아래처럼 쪼갠 뒤,
<p>
<b>
h
<font color="red">
el
</font>
lo
</b>
<i>
w
</i>
orld
</p>
위부터 하나씩 스택에 넣다가 닫는 태그를 발 견한 순간
stack=[
<p>
<b>
h
<font color="red">
el <- 차례대로 스택에 밀어넣다가
]
</font> <- 닫는 태그 발견
lo
</b>
// ...
여는 태그까지 pop 해서 꺼낸 뒤 합쳐서 다시 스택에 넣는 것는다.
stack=[
<p>
<b>
he
<font color="red">le</font> <- 여는 태그까지 스택에서 모두 pop 해와서 합친 뒤 다시 스택에 넣는다.
내용물은 뒤집어서 넣는 것이 핵심
]
o
</b>
<i>
w
</i>
orld
</p>
이 과정을 반복하면 되겠다 싶었다. 아직 디테일이 부족하지만 그건 풀면서 해결하자는 생각에 바로 코드 작성을 진행했다.
풀이
결국 위 풀이 과정에서 생각한 것과 거의 동일한 방법으로 풀었다. 딱 하나 다른 것은 문자열을 바로 스택에 넣는 게 아니라 객체로 만들어 넣는 것이다. 이러면 들어간게 태그인지 문자열인지 이미 한 번 합쳐진 결과물인지 구분이 가능하고, 유연하게 합쳐나갈 수 있다.
function solution(html) {
const stack = [];
while (html.length) {
// 여는 태그인지 닫는 태그인지 관계 없이, 가장 앞의 태그 문자열을 찾는다.
const tag = html.match(/<[^>]+>/)?.[0];
// 태그 문자열이 없으면 반복문을 나간다.
// 정상적인 입력이라면 이 조건에 해당될 일은 없다. 무조건 4 라인의 조건에 의해서만 while 문을 빠져나간다.
if (!tag) {
break;
}
// 6 라인에서 찾은 tag 문자열이 html 에서 어디에 위치하는 지 찾는다.
const tagIndex = html.indexOf(tag);
// 만약 위치가 0보다 크다면 태그 앞에 태그가 아닌 문자열이 존재한다는 뜻이다.
if (tagIndex > 0) {
// 태그가 아닌 문자열을 스택에 넣는다.
// 문자열의 경우에는 스택에 넣을 때 미리 뒤집어서 넣는다.
stack.push({
type: "string",
content: reverseString(html.slice(0, tagIndex)),
});
// 스택에 넣은 문자열은 html 에서 제거한다.
html = html.slice(tagIndex);
}
// tag 가 여는 태그인지 닫는 태그인지 확인한다.
const tagType = tag.match(/<\//) ? "close" : "open";
if (tagType === "open") {
// 여는 태그였다면 스택에 넣는다.
stack.push({ type: tagType, content: tag });
} else {
// 닫는 태그였다면 직전 여는 태그부터 이 태그까지 사이에 있는 컨텐츠들을 뒤집는다.
// `reverseContent` 함수에 대한 자세한 설명은 43 라인을 보자.
reverseContent(stack, tag);
}
html = html.replace(tag, "");
}
return stack[0].content;
}
// 37 라인에서 넘어온다.
function reverseContent(stack, closeTag) {
const contents = [];
// 정상적인 stack 이라면 여는 태그가 무조건 하나 이상 존재하기 때문에
// 54 라인 if 문에 걸려서 이 while 문을 빠져나가게 된다.
// 따라서 while 문의 조건이 true 인 것은 문제 없다.
while(true) {
// 스택에서 pop 한다.
const item = stack.pop();
// pop 한 아이템이 여는 태그였다면
if(item.type === 'open') {
stack.push({
type: 'contents',
// 여태까지 pop 했던 아이템들을 모두 연결한다.
// pop 할 때마다 contents 에 push 해두었기 때문에 .join('') 으로 연결만 해도
// 자연스럽게 순서가 반대가 되어 합쳐진다.
content: `${item.content}${contents.join('')}${closeTag}`,
})
// 그리고 while 문을 빠져나간다.
break;
}
// pop 한 아이템이 여는 태그가 아니었다면 contents 에 아이템을 밀어넣는다.
contents.push(item.content)
}
}
function reverseString(string) {
return string.split('').reverse().join('');
}
후기
처음에는 평소에 본 적 없는 문제라 당황한데다가 쓸데없이 토큰에 꽂혀서 제대로 문제를 풀지 못했다. 잠시 문제를 치워뒀다가 다시 보니 쉬운 방법이 있었는데 돌아가고 있었다는 걸 깨달았고 빨리 해결할 수 있었다.
따라서 오늘의 교훈은 "안 풀릴 때는 잠시 딴 일을 하다 돌아오자." ...물론 시험이나 기술 면접 같은 곳에서는 안 통할 이야기긴 하다.
목차