시리즈 "알고리즘 문제풀기" 개요

  • 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('');
}

후기

처음에는 평소에 본 적 없는 문제라 당황한데다가 쓸데없이 토큰에 꽂혀서 제대로 문제를 풀지 못했다. 잠시 문제를 치워뒀다가 다시 보니 쉬운 방법이 있었는데 돌아가고 있었다는 걸 깨달았고 빨리 해결할 수 있었다.

따라서 오늘의 교훈은 "안 풀릴 때는 잠시 딴 일을 하다 돌아오자." ...물론 시험이나 기술 면접 같은 곳에서는 안 통할 이야기긴 하다.