LeetCode - Reorganize String (Javascript)

문제 설명

같은 문자가 붙어서 나열되지 않도록, string을 재배열 하는 문제다.
만약 같은 문자가 연속으로 나열되지 않는 것이 불가능 하다면 빈 문자열 “”를 반환한다.

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

---

소스 코드

그림을 그려서 규칙을 찾아내니 쉽게 풀 수 있었다.
생각보다 시간 효율성도 굉장히 우수하게 나왔다.

const reorganizeString = (s) => {
  const obj = {};
  [...s].forEach((char) => (obj[char] = obj[char] + 1 || 1));
  const sortedArr = Object.keys(obj).sort((a, b) => obj[b] - obj[a]);
  let max = (s.length + 1) / 2;
  if (obj[sortedArr[0]] > max) return '';
  const result = [];
  let temp;
  let idx = 0;
  for (let i = 0; i < sortedArr.length; i++) {
    temp = obj[sortedArr[i]];
    for (let j = 0; j < temp; j++) {
      if (idx >= s.length) idx = 1;
      result[idx] = sortedArr[i];
      idx += 2;
    }
  }
  return result.join('');
};

---

풀이 설명

아래와 같이 그림을 그린 뒤, 빈 공간을 채워나가는 식으로 풀이했다.

먼저, 위와 같은 기초 배열을 예로 들었을 때 최대 빈도수를 갖는 a를 우선적으로 배치한다고 가정해보자.

그리고 위와 같이 a 사이에 잔여 문자들을 채워 넣는다고 생각하면, 1 → 3 → 5 → 7 순으로 채워져야 한다는 것을 직관적으로 알아차릴 수 있다.

따라서 idx라는 포인터를 두고, 1 → 3 → 5 → 7순으로 result라는 배열에 각 값들을 삽입해주면 끝이다. 물론 여기서 주의해야 할 점은, idx가 s.length를 초과했을 경우 다시 1로 초기화 되어야 한다는 점이다.

따라서 위와 같이 idx의 시작점은 0이므로, idx+=2씩 증가시켜주면, a는 0→2→4→6에 배치되게 된다.
그리고 이후부터 idx가 1로 초기화 되며, 1 → 3 → 5 → 7을 각각 다른 값들이 채워나간다.

---