Portfolio

문제

풀이

재영


class MinHeap {
  constructor() {
    this.heap = [null];
  }
  heappush(val) {
    this.heap.push(val);
    let nowIdx = this.heap.length - 1;
    let parentIdx = this.updateParentIdx(nowIdx);

    while (nowIdx > 1 && this.heap[nowIdx][1] < this.heap[parentIdx][1]) {
      nowIdx = parentIdx;
      parentIdx = this.updateParentIdx(nowIdx);
    }
  }

  heappop() {
    if (this.heap.length === 1) return;
    if (this.heap.length === 2) return this.heap.pop();
    const min = this.heap[1];
    this.heap[1] = this.heap.pop();

    let [nowIdx, leftIdx, rightIdx] = this.updateIndices(1);

    if (!leftIdx) return min;
    if (!rightIdx) {
      if (this.heap[nowIdx][1] > this.heap[leftIdx][1]) {
        this.swap(nowIdx, leftIdx);
        return min;
      }
    }

    while (
      this.heap[leftIdx] !== undefined &&
      this.heap[rightIdx] !== undefined &&
      Math.min(this.heap[leftIdx][1], this.heap[rightIdx][1]) <
        this.heap[nowIdx]
    ) {
      const minIdx =
        this.heap[leftIdx][1] < this.heap[rightIdx][1] ? leftIdx : rightIdx;

      this.swap(nowIdx, minIdx);
      [nowIdx, leftIdx, rightIdx] = this.updateIndices(minIdx);
    }

    return min;
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
  updateParentIdx(idx) {
    return Math.floor(idx / 2);
  }
  updateIndices(idx) {
    return [idx, idx * 2, idx * 2 + 1];
  }
  size() {
    return this.heap.length - 1;
  }
}

const reorganizeString = (s) => {
  const minHeap = new MinHeap(); // 최소 힙
  const counts = {}; // 얘가 숫자를 세줘요 { 겹친 문자: 카운트 수 } aab -> a : 1
  const splitedS = [...s]; // 배열로 만들어주는 거에요 (이유: 문자를 편하게 넣기 위해)

  splitedS.forEach((val, idx) => {
    if (val === splitedS[idx - 1]) { // 이전것과 겹쳤다!
      counts[val] = (counts[val] ?? 0) + 1;
      splitedS[idx - 1] = "";
    }
  });

  Object.entries(counts).forEach((cntArr) => {
    minHeap.heappush([...cntArr, false]);
  });

  let arrangedS = [...splitedS.join("")];
  let lastS = [...arrangedS]; // 이전 결과랑 동일한지 체크해주는 애

  while (minHeap.size()) {
    let [now, cnt, isSecond] = minHeap.heappop();

    if (JSON.stringify(arrangedS) === JSON.stringify(lastS) && isSecond)
      return "";
    lastS = [...arrangedS];
    for (let i = 0; i < arrangedS.length; i += 1) {
      if (!cnt) continue;
      if (arrangedS[i] !== now) {
        if (!i || arrangedS[i - 1] !== now) {
          arrangedS[i] = now + arrangedS[i];
          cnt -= 1;
        } else if (i === arrangedS.length - 1) {
          arrangedS[i] += now;
          cnt -= 1;
        }
      }
    }
    arrangedS = [...arrangedS.join("")];
    if (cnt) {
      minHeap.heappush([now, cnt, true]);
    }
  }

  return arrangedS.join("");
};

효성

풀긴 풀었는데... 풀이가 지저분해요..


class MyHeap {
  constructor() {
    this.heap = []; // n:parent, 2*n+1:left child, 2*n+2:right child
  }
  size() {
    return this.heap.length;
  }
  push(node) {
    this.heap.push(node);
    let curIdx = this.heap.length - 1;
    let parentIdx = Math.floor((curIdx - 1) / 2);

    while (this.heap[parentIdx] < this.heap[curIdx]) {
      [this.heap[parentIdx], this.heap[curIdx]] = [
        this.heap[curIdx],
        this.heap[parentIdx],
      ];
      curIdx = parentIdx;
      parentIdx = Math.floor((curIdx - 1) / 2);
    }
  }

  pop() {
    let lastIdx = this.heap.length - 1;
    let curIdx = 0;
    [this.heap[curIdx], this.heap[lastIdx]] = [
      this.heap[lastIdx],
      this.heap[curIdx],
    ];
    const result = this.heap.pop();
    lastIdx = this.heap.length - 1;

    while (curIdx < lastIdx) {
      let leftIdx = curIdx * 2 + 1;
      let rightIdx = curIdx * 2 + 2;
      if (this.heap[leftIdx] == null) break;
      if (this.heap[rightIdx] == null) {
        if (this.heap[curIdx] < this.heap[leftIdx]) {
          [this.heap[curIdx], this.heap[leftIdx]] = [
            this.heap[leftIdx],
            this.heap[curIdx],
          ];
        }
        curIdx = leftIdx;
        break;
      }

      if (
        this.heap[curIdx] < this.heap[leftIdx] ||
        this.heap[curIdx] < this.heap[rightIdx]
      ) {
        const maxIdx =
          this.heap[leftIdx] > this.heap[rightIdx] ? leftIdx : rightIdx;
        [this.heap[curIdx], this.heap[maxIdx]] = [
          this.heap[maxIdx],
          this.heap[curIdx],
        ];
        curIdx = maxIdx;
      } else {
        break;
      }
    }
    return result;
  }
}

var reorganizeString = function(s) {
    const counter = {};
    s.split('').forEach((x) => { 
      counter[x] = (counter[x] || 0)+1; 
    });
    const sortable = Object.entries(counter)
        .sort(([, a], [, b]) => b-a)
        .reduce((r, [k, v]) => ({ ...r, [k]: v }), {});
    
    let answer = '', checker = '', max = 0, idx = 0;
    let keys = Object.keys(sortable);
    let values = Object.values(sortable);
    const heap = new MyHeap();
    
    values.forEach(cnt => heap.push(cnt));
    while(heap.size() > 0) {
        max = heap.pop();
        idx = values.indexOf(max);
        if(checker !== keys[idx] && max !== 0) {
            answer += keys[idx];
            checker = keys[idx];
            values[idx]--;
            if(values[idx]) {
                heap.push(values[idx]);
            }
        }
        else if(checker === keys[idx] && max !== 0) {
            let tempValue = values[idx];
            let tempValueIdx = idx;
            values[idx] = 0;
            max = heap.pop();
            idx = values.indexOf(max);
            if(!keys[idx]) {
                return "";
            }
            answer += keys[idx];
            checker = keys[idx];
            values[idx]--;
            if(values[idx]) {
                heap.push(values[idx]);
            }
            heap.push(tempValue);
            values[tempValueIdx] = tempValue;
        }
    }
    return answer;
}

은찬


const asc = (a, b) => {
    if(a[1] === b[1]){
        return a[0] - b[0];
    }

    return b[1] - a[1];
}
    
const reorganizeString = (s) => {
    const map = new Map();
    const answer = [];
    let beforeChar = "";
    
    for(let i = 0; i < s.length; i++){
        const count = map.get(s[i]);
        
        map.set(s[i], count ? count + 1 : 1);
    }
    
    const orderedMap = [...map.entries()].sort(asc);
    
    console.log(orderedMap);
    
    while(orderedMap.length){
        let keep = false;
        
        for(let i = 0; i < orderedMap.length; i++){
            const [k, v] = orderedMap[i];
            
            if(beforeChar !== k){
                keep = true;
                answer.push(k);
                beforeChar = k;
                
                if(v - 1){
                    orderedMap[i][1] = v - 1;
                } else{
                    orderedMap.splice(i, 1);
                }
                break;
            }
        }
        
        if(!keep){
            return "";
        }
        
        orderedMap.sort(asc);        
    }
    
    return answer.join("");
};

Reorganize String

문제

풀이

풀긴 풀었는데... 풀이가 지저분해요..