[프로그래머스][LEVEL3] 110 옮기기

# 문제 원문

 

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

코딩테스트 연습 - 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

---

입출력 예

s / result

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

["1101","100110110","01101101

# 문제 풀이

 

쉬워보이면서 어려운 문제이다. 가볍게 보고 접근하면 고생을 많이 한다. 특히 효율성 측면에서 해당 문제를 풀면서 시간 복잡도와 공간복잡도에 대한 이해가 부족하다는 점을 새삼 느꼈다. 그리고 문제를 설계 하는 부분을 좀 더 집중해서 개선 할 필요성을 느꼈다. 문제 자체는 입력 받은 s라는 0과 1로 이루어진 문자열 배열에서 110이라는 문자열을 찾아서 옮기며 사전순으로 가장 빠른 문자열을 만들어 반환하는 문제이다.

 

첫번째 핵심은사전순으로 보았을때 0이 1보다 빠르다는 사실을 캐치하는것이다. 0이 1보다 빠르다는 것을 캐치했다면 최대한 0이 1보다 앞에 있는 문자열을 만들어서 반환해야한다는 사실을 알 수 있다.

 

두번째 핵심은 110이라는 문자열을 만들 수 있는 경우를 모두 반복해서 제거해가면서 카운팅해야한다는 것과 그것을 모두 하나로 합쳐서 특정 위치에 삽입해야한다는 것을 아는 것이다. 여기서 단순 문자열 처리라는 방법으로 반복해서 접근할 경우 백만 * 백만이라는 시간 복잡도 때문에 시간초과를 경험하게 된다. (110을 '한번' 찾을때마다 문자열을 전부 스캔해야하기 때문이다.) 탐색에 사용되는 시간을 스택구조를 활용해서 최소화 시켜야한다.

 

세번째 핵심은 110을 모두 제거하고 남은 문자열에서 110묶음을 삽입할 적절한 위치를 찾는 것이다. 이것을 만약 두번째 방법처럼 원소를 삽입 & 삭제를 반복하면서 처리한다면 js에서는 단순 배열로 처리할 시 시간 초과가 난다. 가장 앞의 요소 부터 체크한다면 shift 연산과 unshift 연산에서 배열에 속한 모든 요소를 한자리씩 밀고 당기기 때문이다. 그러니 stack이라는 자료구조를 끝까지 지켜서 pop, push 연산을 해줘야한다. 아니라면 idx를 직접 찾아서 구조 변경 비용을 최소화 시켜줘야한다.

 

필요한 처리를 마친 문자열을 다시 동일한 순서로 반환하면 되는 문제이다. 가볍게 접근하기 쉬워보이지만 풀면 풀수록 처음 설계를 제대로 안한 것이 난관으로 작용 했던 문제 였던거 같다.

 

# 솔루션 플로우

1. 입력 받은 s를 순회한다.

2. 입력 받은 s의 문자열에서 110을 찾을 수 없다면 그대로 반환해준다.

3. 110을 찾을 수 있다면 스택을 활용하여서 문자열을 탐색하면서 나올 수 있는 모든 110을 찾아서 제거해준후 그 110을 따로 합쳐준다.

4. 사전 순으로 최대한 0이 앞에 있을 수 있게 문자열들을 합쳐준다.

5. 그렇게 구해진 문자열 배열을 반환한다.

1. 스택을 활용한 풀이

function solution(s) {
  return s.reduce((result, current) => {
    if (current.includes('110')) {
      const stack = [];
      let count = 0;
      for (const right of current) {
        if (stack.length > 1) {
          const mid = stack.pop();
          const left = stack.pop();
          `${left}${mid}${right}` === '110'
            ? count++
            : stack.push(left, mid, right);
        } else {
          stack.push(right);
        }
      }
      const answer = [];
      while (stack.length > 0) {
        const currentChar = stack.pop();
        if (currentChar === '0') {
          stack.push(currentChar);
          break;
        }
        answer.push(currentChar);
      }
      answer.push(''.padStart(count * 3, '110'));
      while (stack.length > 0) answer.push(stack.pop());

      result.push(answer.reverse().join(''));
    } else {
      result.push(current);
    }

    return result;
  }, []);
}