[BOJ] 9177. 단어 섞기 (JavaScript)

gitgitWi's TIL·2021년 2월 9일
0

BOJ 도장깨기

목록 보기
3/4

9177. 단어 섞기

문제 요약

  • 문자열 a, b의 알파벳들을 섞은 문자열 c
  • a, b 각각의 문자 순서가 c에도 유지되고 있는지?

회고

이 문제의 출제의도는 대체..?

  • 알고리즘 분류를 안 보이게 해놨더니, 출제의도 파악하기가 쉽지 않았다
  • 문제 자체가 심플하고 왠지 만만해 보이기 때문에(?) 투 포인터 잘 쓰면 되겠지하고 접근했다가, 동일한 알파벳이 a, b 모두 해당되는 경우 연산 잘못되는 문제를 발견했다
  • 이후 백트래킹 관점으로 접근했다가 계속해서 채점 50%에서 틀리거나, 시간 초과가 발생했다
  • 결국, 내가 모르는 문자열 알고리즘이 있는건가 싶어서 검색을 했는데..
  • 방향은 맞았는데, memoization을 제대로 안한 것이 문제였다

시간초과 문제를 접근하는 방법

  • 연산량이 좀 과하게 많다 싶으면, DP 또는 이분 탐색 가능성 큼
  • 재귀 콜스택 문제일 수 있는 경우 iteration으로 전환
    • 그래도 안되면 memoization을 확인
    • 그래도 안되면 애초에 접근 방식이 잘못 되었을 수도
  • 이번 문제에서는 memoization을 제대로 안해서 문제가 있었음
    • 아래 풀이와 같이 간단하게 2차원 배열로 인덱스 접근하면 되는데,
    • 만들어진 문자열을 Set에 넣고 비교하는 비효율적인 방식으로 만들었었다
    • memoization은 최대한 빠르게 접근할 수 있도록 만들자

재귀냐 iteration이냐

  • 이 문제도 역시 재귀, iteration 둘다 사용해 풀 수 있다
  • 재귀를 사용하면 시간은 좀더 빠르고 메모리는 좀더 쓰게 됨


하아..도장 깨기하다 내 머리가 깨지는 중..

/**
 * canMakeRecursion
 * 재귀를 활용해 탐색하는 함수
 * 
 * @param {string} a 입력된 a 문자열
 * @param {string} b 입력된 b 문자열
 * @param {string} c 입력된 c 문자열
 * @param {string} aStr 만들고 있는 a 문자열
 * @param {string} bStr 만들고 있는 b 문자열
 * @param {string} cIdx c의 현재 포인터 위치
 * @param {boolean[][]} visited 메모이제이션; aStr, bStr 인덱스 기록
 * @returns {boolean} 단어가 만들어질 수 있는지 아닌지
 */
const canMakeRecursion = (a, b, c, aStr, bStr, cIdx, visited) => {

  // 문자열 C의 모든 문자를 탐색한 경우
  if (cIdx === c.length) {
    return aStr === a && bStr === b;
  };

  const curr = c[cIdx];
  const aIdx = aStr.length;
  const bIdx = bStr.length;

  // 다른 재귀에서 이미 방문한 문자열이면 return false
  // 최초 방문이면 방문 처리
  if (visited[aIdx][bIdx]) return false;
  visited[aIdx][bIdx] = true;

  // recursion processing
  // 현재 문자가 a 포인터 문자와 같은 경우
  if (a[aIdx] === curr) {
    const isNextOK = canMakeRecursion(a, b, c, aStr + curr, bStr, cIdx + 1, visited);
    if (isNextOK) return true;
  };

  // 현재 문자가 b 포인터 문자와 같은 경우
  if (b[bIdx] === curr) {
    const isNextOK = canMakeRecursion(a, b, c, aStr, bStr + curr, cIdx + 1, visited);
    if (isNextOK) return true;
  };

  // 위 두 경우 모두 해당되지 않으면 return false
  return false;
};

/**
 * canMakeIteration
 * while iteration을 활용해 탐색하는 경우
 * 
 * @param {string} a 입력된 a 문자열
 * @param {string} b 입력된 b 문자열
 * @param {string} c 입력된 c 문자열
 */
const canMakeIteration = (a, b, c) => {
  // 방문 기록
  const visited = Array.from({ length: a.length + 1 }, () => Array(b.length + 1).fill(false));

  // initialization
  let aStr = "", bStr = "";
  const queue = [];
  queue.push({ prevA: aStr, prevB: bStr });

  // 문자열 C의 모든 문자에 대해 하나씩 탐색
  for (let cIdx = 0; cIdx < c.length; cIdx++) {

    // C의 특정 문자에 대해 탐색
    let currLoop = queue.length;
    while (currLoop--) {
      const currStr = c[cIdx];
      const { prevA, prevB } = queue.shift();

      const aIdx = prevA.length, bIdx = prevB.length;

      // 방문 처리
      if (visited[aIdx][bIdx]) continue;
      visited[aIdx][bIdx] = true;

      // 현재 문자가 a 포인터 문자와 같은 경우
      // 만들어지는 문자열에 대해서는 바로 업데이트
      if (a[aIdx] === currStr) {
        aStr = prevA + currStr;
        queue.push({ prevA: aStr, prevB });
      };

      // 현재 문자가 b 포인터 문자와 같은 경우
      if (b[bIdx] === currStr) {
        bStr = prevB + currStr;
        queue.push({ prevA, prevB: bStr });
      };
    };
  };

  // 최종 결과가 a, b와 같은지 비교해 return
  return aStr === a && bStr === b;
};

const solution = (arr) => {
  const q = arr.slice(1).map(line => line.split(" "));

  // IO 시간 단축 위해 결과값을 일단 arr로 저장
  let ans = [];

  for (const idx in q) {
    const [a, b, c] = q[idx];

    // iteration으로 탐색하는 경우
    // const res = canMakeIteration(a, b, c);

    // recursion으로 탐색하는 경우
    const visited = Array.from({ length: a.length + 1 }, () => Array(b.length + 1).fill(false));
    const res = canMakeRecursion(a, b, c, "", "", 0, visited);

    ans.push(`Data set ${+idx + 1}: ${res ? 'yes' : 'no'}`);
  };

  return ans.join("\n");
};

/*
const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
  prompt: ""
});
const q = [];
rl.on("line", (line) => {
  line 
    ? q.push(line) 
    : rl.close();
}).on("close", () => {
  console.log(solution(q));
  process.exit();
});
*/
profile
가볍게 TIL 남기는 velog, 꾸준히 성장하는 개발자

0개의 댓글