[프로그래머스] LV.3 110 옮기기 (JS)

문제

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
  

입출력 예시

s	result
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

풀이

2021 월간 코드 챌린지 시즌2에 출제된 따끈따끈한 문제다. 어떤 배치를 택해야 사전순으로 가장 앞으로 나열할 수 있는지와 그 방법에 대한 고민이 적절히 필요하다.

1) 사전순 나열

먼저 110을 어떻게 배치해야 사전순으로 가장 앞설 수 있는지 생각해보자. 110은 0과 1을 3개 이용하여 만들어지는 문자열 조합이다. 사전순으로는 0이 1보다 앞서므로 만약 3개의 글자만 있다면 다음과 같은 순서가 가능하다.

• 000 - 001 - 010 - 011 - 100 - 101 - 110 - 111

따라서 110이 주어진 문자열보다 사전순으로 더 앞선 위치에 배치되기 위해서는 문자열 내에 연속되는 1이 있다면 그 시작점 보다 앞에 위치해야 한다. 왜냐하면 주어진 0과 1이 아무리 많아도 110보다 사전 순으로 더 늦게 나올 수 있는 경우의 수는 11... 부터 가능성이 생기기 때문이다. 즉 110을 모두 추출하고나서 연속되는 1의 위치를 찾아 그 위치부터 추출한 110을 붙여 넣는다면 가장 빠른 변형된 문자열을 완성시킬 수 있을 것이다.

2) 스택을 활용한 모든 110 탐색

일단 문자열에서 110을 모조리 찾아야한다. 이때 주의해야 할 점은 주어진 문자열에서 한번에 모조리 찾는 것이 아니라 하나씩 찾는 과정을 반복해야 하는 것이다. 예를 들어 101110101110이라는 문자열이 있을때 여기서 110을 한 번에 찾으면 다음과 같이 2개가 존재한다.

• 101110101110

그러나 한 개씩 찾으며 해당 문자열을 제거해 나간다면 다음과 같이 3개의 110을 찾을 수 있다.

• 101110101110 - 110 제외
• 101101110 - 110 제외
• 101110 - 110 제외
• 101

문제에서 주어진 예시#3번을 보면 위와 같이 추출된 110으로 인해 새로운 110이 만들어지면 이 역시 추출하는 것을 볼 수 있다. 따라서 우리는 후자의 방법으로 하나씩 110을 추출하고, 새로 만들어진 문자열에 대해서도 이를 적용해야 한다.

이를 위해서는 무한루프를 돌며 replace() 메서드를 사용하여 문자열 자체를 치환하는 방식 또는 split() 메서드를 사용해 분리하는 방식 등 다양한 접근이 가능하지만 문제는 제한 사항에 있다. 주어진 문자열 배열 s의 길이는 최대 100만이고, 각 원소의 길이 역시 100만이기 때문에 위와 같은 방식으로는 중첩 반복문의 구조가 되어 시간초과가 날 확률이 높다. 따라서 우리는 110 추출을 최대한 선형시간 O(N)안에 수행해야한다.

이를 위해 스택을 이용하자. 주어진 문자열을 한 문자 단위로 분리하고 하나씩 접근하며 지금 들어가는 문자와 이전에 들어간 문자를 비교해 110이 만들어지는 순간을 체크하도록 한다면 선형시간으로 추출이 가능하다. 다음 코드를 직접 보자.

for(const _s of s) {
  // 현재 문자열에서 110을 제외한 문자를 저장할 스택 선언
  const stack = [];
  // 현재 문자열을 개별 문자단위로 분리
  const arr = _s.split('');
  // 110이 등장한 횟수 체크
  let count = 0;
  
  for(let i = 0; i < arr.length; i++) {
    // 현재 문자를 세번째 문자로 계산하여 접근한다.
    // 즉 110에서 0의 위치를 담당한다.
    const third = arr[i];
    
    // 스택의 길이가 1보다 큰 경우엔 최소 2개의 원소가 존재
    // 따라서 최근에 들어간 2개의 원소에 접근하여
    // 각각 원소의 값이 1,1,0 인지 체크한다.
    if(stack.length > 1) {
      // 스택은 LIFO 구조이므로
      // pop 하는 순서의 역순으로 위치를 정해준다.
      // 즉 마지막에 pop하는 원소가 첫번째 자리가 된다.
      const second = stack.pop();
      const first = stack.pop();
      
      // 추출한 3개의 원소가 앞에서부터 비교해 110이 된다면
      if(first === '1' && second === '1' && third === '0') {
        // 110이 등장한 횟수를 하나 올리고 반복 계속
        // pop을 통해 기존 원소가 추출되었으므로
        // 다음의 원소는 이들이 제외된 상태에서
        // 새로운 110이 만들어지는지 체크가 가능하다
        count++;
        continue;
      } else {
        // pop을 했지만 110이 만들어지지 않은 경우이므로
        // 다시 이들 값을 순서대로 push
        stack.push(first, second, third);
      }
    } else {
      // 스택의 원소 개수가 2개보다 작은 경우엔
      // 110을 만들수 없기 때문에 그냥 push
      stack.push(third);
    }
  }

위와 같이 pop()과 push() 메서드를 통해 선형시간 내에 110을 모두 제외한 문자열이 담긴 배열을 만들어줄 수 있다.

3) 110 재배치

위에서 구한 stack에는 110을 모두 제외한 문자가 배열로 담겨있다. 그리고 110이 등장한 횟수는 count에 담겨있다. 추출한 110은 모두 등장횟수 count만큼 연달아 배치가 가능하다. 110110110...으로 구성된 문자열은 위에서 언급한 순서와 같이 절대 101 이전 순서 앞으로는 등장할 수 없기 때문이다.

따라서 연속된 110의 문자열은 가장 처음 만나는 연속된 1의 시작점에 배치될 수 있다. 예를 들어 110을 모두 추출하고 ...001111과 같은 문자열만 남아있었다면, 추출된 모든 110은 1111앞에 배치되어야 한다. 0을 만나는 순간, 이때의 문자열 순서는 101 또는 001의 조합이 될 수 있기 때문에 그 앞으로는 넘어갈 수 없다.

이때 만약 추출된 110이 없는 경우라면 기존 문자열 자체가 가장 빠른 사전 순 배열이다. 이는 110이 문자열에 존재하는 경우에만 변형이 가능하므로 지극히 당연한 결과이다.

따라서 연속되는 1이 끝나는 지점을 앞서 구한 stack을 이용해 구해주자. 현재 stack에는 110으로 구성이 불가능한 원소들만이 남아있고, 이는 0과 1로 이루어져 있다. 따라서 똑같이 pop()을 하면서 마지막 원소가 1이라면 계속 pop()을 진행하고 0인 경우에는 반복문을 중지하도록 하자.

// 110 구성이 불가한 경우라면 원본 문자열 자체가 정답이다.
if (!count) {
  answer.push(_s);
} else {
  // stack에서 추출되는 문자를 저장할 배열
  const list = [];
  
  while(stack.length) {
    // 스택의 가장 마지막 원소를 추출하여
    const last = stack.pop();
    
    if(last === '0') {
      // 0인 경우에는 다시 이 값을 스택에 넣어주고
      // 중단하도록 해야한다.
      stack.push(last);
      break;
    }
    
    // 이 값이 0이 아닌 경우에 list에 푸시
    list.push(last);
  }
  
  ...
}

위의 과정을 거치면 뒤에서부터 남아있는 연속되는 1은 모두 stack에서 제거될 것이다. 따라서 list에는 연속되는 1의 문자열 나열이 들어가고, stack에는 110이 절대 앞서 위치할 수 없는 문자열 나열이 들어있게 된다. 따라서 현재 만들어진 list에 110의 값을 count 값만큼 넣어주도록 하자. 이때 주의해야 할 점은 stack의 뒤에서부터 역순으로 접근하고 있기 때문에 list에 들어가야할 110의 형태도 역순으로 들어가야 한다는 점이다. 다음과 같이 전개연산자를 이용해 역순으로 list에 푸시하자.

...
// 역순으로 접근하고 있기 때문에 110 역시 역순으로 배치하자
const keyword = "011";

while(count) {
  list.push(...keyword);
  count--;
}

...

마지막으로 stack에 남아있는 원소들을 똑같이 역순으로 list에 삽입하면 된다.

...

while(stack.length) {
  list.push(stack.pop());
}

위 3번의 반복문을 거치면 list에는 변형을 마치고 사전순으로 가장 빠르게 위치한 문자열이 역순으로 저장된다. 초반부터 마지막 원소 먼저 접근했기 때문에 저장된 결과 역시 역순이라는 점을 주의하자. 따라서 이 배열을 역순으로 배치후에 문자열로 만들어주면 문제에서 요구하는 문자열을 만들어 줄 수 있다.

// 역순으로 정렬 후 문자열로 합쳐준다.
const result = list.reverse().join('');
answer.push(result);

4) 전체코드

그리디하게 접근이 가능하지만, 선형시간 안에 110을 추출하는 방법을 떠올리지 못한다면 시간초과로 꽤나 까다로웠을 문제같다. 주석을 제외한 전체코드는 다음과 같다.

function solution(s) {
  const answer = [];
  
  for(const _s of s) {
    const stack = [];
    const arr = _s.split('');
    let count = 0;
    
    for(let i = 0; i < arr.length; i++) {
      const third = arr[i];
      
      if(stack.length > 1) {
        const second = stack.pop();
        const first = stack.pop();
        
        if(first === '1' && second === '1' && third === '0') {
          count++;
          continue;
        } else {
          stack.push(first, second, third);
        }
      } else {
        stack.push(third);
      }
    }
    
    if(!count) {
      answer.push(_s);
    } else {
      const list = [];
      const keyword = "011";
      
      while(stack.length) {
        const last = stack.pop();
        
        if(last === '0') {
          stack.push(last);
          break;
        }
        
        list.push(last);
      }
      
      while(count) {
        list.push(...keyword);
        count--;
      }
      
      while(stack.length) {
        list.push(stack.pop());
      }
      
      const result = list.reverse().join('');
      answer.push(result);
    }
  }
  
  return answer;
}

출처

https://programmers.co.kr/learn/courses/30/lessons/77886