[Algorithm] 110 옮기기

📋 문제

0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.

• x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.

예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.

변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ s의 길이 ≤ 1,000,000
• 1 ≤ s의 각 원소 길이 ≤ 1,000,000
• 1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000

 

입출력 예

["1110","100111100","0111111010"]

["1101","100110110","0110110111"]

 

✏️ 풀이

먼저 '110'을 모두 찾는 것이 중요하다고 생각했다. 찾은 '110'을 적절한 위치에 배치함으로서 문제를 해결하려고 했다. 주의해야하는 것은 '110'을 찾을 때 찾은 '110'을 제거하고 다시 살펴봐야하는 것이다. 예시에 있는 '0111111010'을 보면 '110'은 한번 등장한다. 하지만 찾은 '110'을 제거해보면 '0111110'으로 제일 마지막에 '110'이 또 등장한다.

 

이렇게 찾은 '110'들은 '110'을 제거한 문자열에서 제일 마지막에 등장하는 0뒤에 붙여줘야 한다. 그 이유는 다음과 같다.

• 뒤에 '1'만 등장하므로 '110'이 우선순위를 가진다.
• '1'과 '0'을 조합하여 세자리 문자열을 만들면 '000', '001', '010', '011', '100', '101', '110', '111'로 '110'은 0이 들어가는 문자열 중 가장 마지막 우선순위를 가진다. 

이런 접근방법을 사용해서 문제를 풀었다.

 

가장 먼저 시도한 방법은 match와 replace를 이용해서 110을 찾는 방법이었다. while문으로 돌리면서 str.match(/110/)으로 탐색하고 replace로 제거했다. 이후 '110'이 제거된 문자열을 for문으로 뒤에서 부터 탐색하며 0인 경우 아닌 경우에 따라 더해줬다. 하지만 match와 replace이 전체 문자열을 탐색하기 때문인지 시간초과가 났다.

 

두 번째로는 배열을 사용했다. for문으로 앞에서부터 문자열을 탐색하며 0이 등장한 경우 배열(arr)에 들어간 요소 중 마지막, 마지막 - 1 인덱스의 값을 판별하여 둘다 1인 경우 '110'이 이루어지기 때문에 배열에서 빼주고 '110'의 개수를 의미하는 cnt 변수를 1 증가시켰다. 이후 뒤에서부터 배열(arr)을 순회하며 0이 등장하면 '110'을 cnt만큼 더해주고 배열(arr)의 요소도 더해줬다. 만약 배열에 있는 요소들이 모두 1인 경우를 고려해 cnt만큼 '110'이 더해지지 않았다면 마지막에 제일 앞에 더해주고 만들어진 '1'과 '0'으로 이루어진 문자열을 answer에 넣어줬다.

 

⌨️ 코드

function solution(s) {
  var answer = [];

  for (let str of s) {
    if (str.length <= 3) {
      answer.push(str);
      continue;
    }

    const arr = [];
    let cnt = 0;
    for (const n of str) {
      let flag = false;
      if (n === '0') {
        if (arr.length >= 2) {
          if (arr[arr.length - 1] === '1' && arr[arr.length - 2] === '1') {
            arr.pop();
            arr.pop();
            cnt += 1;
            flag = true;
          }
        }
      }

      if (!flag) arr.push(n);
    }

    let subStr = '';
    for (let i = arr.length - 1; i >= 0; i--) {
      if (arr[i] === '0' && cnt) {
        subStr = '110'.repeat(cnt) + subStr;
        cnt = 0;
      }
      subStr = arr[i] + subStr;
    }
    if (cnt) subStr = '110'.repeat(cnt) + subStr;

    answer.push(subStr);
  }

  return answer;
}