[프로그래머스] 문자열과 알파벳과 쿼리 (JavaScript)

문제 설명[링크]

알파벳 소문자로 이루어진 초기 문자열 s가 주어집니다.
초기 문자열에 포함된 모든 문자들은 고유한 번호를 가지며, n번 문자는 초기 문자열의 n번째 문자를 의미합니다.
예를 들어, 초기 문자열이 "aba"라면 1번 문자는 a, 2번 문자는 b, 3번 문자는 a입니다. 그 후, 초기 문자열에서 1번 문자를 분리해 "a" / "ba" 두 개의 문자열로 나눠졌다면, "a"는 1번 문자로 이루어진 문자열이고 "ba"는 2번 문자와 3번 문자로 이루어진 문자열입니다.

당신은 주어진 문자열에 대해 다음과 같은 5가지 쿼리를 수행해야 합니다. 쿼리는 모두 문자열로 주어집니다.

1 x y : 숫자 1과 정수 x, y가 공백 하나를 사이에 두고 주어집니다. x번 문자와 y번 문자가 같은 문자열에 포함돼 있는지 확인합니다. 같은 문자열에 포함되어 있으면 "YES"를, 포함되어있지 않으면 "NO"를 result 배열의 뒤에 추가합니다.
2 x word : 숫자 2와 정수 x, 문자열 word가 공백 하나를 사이에 두고 주어집니다. x번 문자가 있는 문자열을 찾습니다. 해당 문자열에서 word에 포함된 알파벳을 모두 새로 생성한 빈 문자열로 옮깁니다.
3 x y word : 숫자 3과 정수 x, y가 공백 하나를 사이에 두고 주어집니다. 빈 문자열을 생성한 뒤, x~y번 문자들 중 word에 포함된 알파벳을 모두 새로 생성한 빈 문자열로 옮깁니다.
4 x y : 숫자 4와 정수 x, y가 공백 하나를 사이에 두고 주어집니다. x번 문자가 포함된 문자열과 y번 문자가 포함된 문자열을 하나의 문자열로 합칩니다. 먼저 생성된 문자열에 늦게 생성된 문자열이 합쳐지는 형식으로 먼저 생성된 문자열만 남고 늦게 생성된 문자열은 사라집니다.
5 : 숫자 5가 주어집니다. 항상 쿼리의 마지막에 한 번만 주어집니다. 존재하는 모든 문자열에 대해 문자열의 알파벳 구성을 각각 result 배열의 뒤에 추가합니다. 모든 문자열의 알파벳 구성을 문자열이 먼저 생성된 순으로 result 배열의 뒤에 추가합니다.
유의 사항은 다음과 같습니다.

같은 문자열 안에 있는 문자들은 항상 번호순으로 정렬합니다.
문자열의 길이가 0이 되면 해당 문자열은 사라집니다.
문자열의 알파벳 구성은 다음과 같습니다.

문자열의 알파벳 구성은 하나의 문자열입니다.
a부터 z까지 사전 순으로 알파벳과, 해당 알파벳이 문자열에 포함된 개수를 공백 하나로 구분한 형태입니다.
예를 들어, "abaebae" 처럼 a 3개, b 2개, e 2개로 이루어진 문자열의 알파벳 구성은 "a 3 b 2 e 2"입니다.
초기 문자열 s와 쿼리를 담고 있는 문자열 배열 query가 주어집니다. 쿼리를 주어진 순서대로 모두 마친 후의 result 배열을 return 하도록 solution 함수를 완성해 주세요.

풀이

• 각 알파벳(26개)에 대한 위치와, 관계를 SegmentTree와 UnionFind로 구성
• 1번 쿼리: 세그트리에서 조회하고자 하는 ID에 대한 쿼리
  • 해당 ID는 2, 3, 4번 쿼리에 의해 관계가 바뀔 수 있음
  • 해당 바뀐 관계는 UF.find와, updates 배열의 rep값을 참조하여 검색
• 2번 쿼리: 해당 알파벳에 대한 특정 위치에 id값을 검색하여, 해당 id값이 참조하고 있는 updates 배열의 위치 index를 찾아 해당 값을 업데이트 하려는 groupId로 대체
• 3번 쿼리: 해당하는 알파벳 Lazy Segtree에서 해당 범위에 대해 업데이트
• 4번 쿼리: union하려는 두 id값을 모든 세그트리를 순회해서, 만약 큰 id가 updates배열에 없다면 pass하고, 작은id가 없다면 생성 후, map에 등록해주고, uf를 통해 union시킴
  • st.query()가 해당 union을 반영해야 하기 때문에 updates배열 탐색하는 index에 uf.find를 적용

let groupId = 0;

class SegmentTree {
  constructor(n) {
    this.n = n;
    this.tree = new Array(4 * n).fill(0);
    this.lazy = new Array(4 * n).fill(0);
    this.updates = [0];
    this.map = new Map();
    this.map.set(0, 0);

    this.root = new Array(200000).fill().map((_, index) => index);
  }

  mergeRep(x, y) {
    if (!this.map.has(y)) return;
    const yIndex = this._find(this.map.get(y));
    if (!this.map.has(x)) {
      this.updates.push(x);
      this.map.set(x, this.updates.length - 1);
    }
    const xIndex = this._find(this.map.get(x));
    this.root[yIndex] = xIndex;
  }

  _find(x) {
    if (this.root[x] === x) return x;
    return (this.root[x] = this._find(this.root[x]));
  }

  moveRep(x, id) {
    if (!this.map.has(x)) return;
    const updateIndex = this._find(this.map.get(x));
    x = this.updates[updateIndex];
    this.updates[updateIndex] = id;
    this.map.delete(x);
    this.map.set(id, updateIndex);
  }

  _push(node, start, end) {
    if (this.lazy[node] !== 0) {
      this.tree[node] = this.lazy[node];
      if (start !== end) {
        this.lazy[node * 2 + 1] = this.lazy[node];
        this.lazy[node * 2 + 2] = this.lazy[node];
      }
      this.lazy[node] = 0;
    }
  }

  _updateRange(node, start, end, l, r, v) {
    this._push(node, start, end);
    if (end < l || r < start) return;
    if (l <= start && end <= r) {
      this.tree[node] = v;
      if (start !== end) {
        this.lazy[node * 2 + 1] = v;
        this.lazy[node * 2 + 2] = v;
      }
      return;
    }

    const mid = Math.floor((start + end) / 2);
    this._updateRange(node * 2 + 1, start, mid, l, r, v);
    this._updateRange(node * 2 + 2, mid + 1, end, l, r, v);

    const leftVal = this.tree[node * 2 + 1];
    const rightVal = this.tree[node * 2 + 2];
    this.tree[node] = leftVal > rightVal ? leftVal : rightVal;
  }

  updateRange(l, r, id) {
    this.updates.push(id);
    const newIndex = this.updates.length - 1;
    this.map.set(id, newIndex);
    this._updateRange(0, 0, this.n - 1, l, r, newIndex);
  }

  _query(node, start, end, idx) {
    this._push(node, start, end);
    if (start === end) return this.tree[node];
    const mid = Math.floor((start + end) / 2);
    if (idx <= mid) return this._query(node * 2 + 1, start, mid, idx);
    return this._query(node * 2 + 2, mid + 1, end, idx);
  }

  indexQuery(x) {
    return this._query(0, 0, this.n - 1, x);
  }

  query(x) {
    return this.updates[this._find(this.indexQuery(x))];
  }
}

const convertWord = word => word.split('').map(el => el.charCodeAt() - 97);
const ALPHA_LEN = 26;

function solution(s, queries) {
  queries = queries.map(el => el.split(' '));
  s = convertWord(s);
  const n = s.length;
  const sts = new Array(ALPHA_LEN).fill().map(() => new SegmentTree(n));
  const res = [];

  for (const [fl, ...args] of queries) {
    if (fl === '1') {
      const x = +args[0] - 1;
      const y = +args[1] - 1;
      const xid = sts[s[x]].query(x);
      const yid = sts[s[y]].query(y);
      if (xid === yid) res.push('YES');
      else res.push('NO');
    } else if (fl === '2') {
      groupId++;
      const x = +args[0] - 1;
      const word = new Set(convertWord(args[1]));
      const id = sts[s[x]].query(x);
      for (const c of word) {
        sts[c].moveRep(id, groupId);
      }
    } else if (fl === '3') {
      groupId++;
      const x = +args[0] - 1;
      const y = +args[1] - 1;
      const word = new Set(convertWord(args[2]));
      for (const c of word) {
        sts[c].updateRange(x, y, groupId);
      }
    } else if (fl === '4') {
      const x = +args[0] - 1;
      const y = +args[1] - 1;
      let xid = sts[s[x]].query(x);
      let yid = sts[s[y]].query(y);
      if (xid > yid) [xid, yid] = [yid, xid];
      for (const st of sts) {
        st.mergeRep(xid, yid);
      }
    } else if (fl === '5') {
      const bucket = [];
      const collectBox = new Array(groupId + 1)
        .fill()
        .map(() => new Array(26).fill(0));

      for (let x = 0; x < n; x++) {
        const id = sts[s[x]].query(x);
        collectBox[id][s[x]]++;
      }

      for (const collect of collectBox) {
        const box = [];
        for (let i = 0; i < 26; i++) {
          if (!collect[i]) continue;
          box.push(String.fromCharCode(97 + i));
          box.push(collect[i]);
        }
        if (box.length) bucket.push(box.join(' '));
      }
      res.push(...bucket);
    }
  }

  return res;
}