🔎 110 옮기기

❓ 문제링크

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

📄 제출 코드

const answer = [];
function solution(s) {
  for (let t = 0; t < s.length; t++) {
    let str = s[t]
    let stack = [];
    let tmp = find110(str, stack);
    console.log(`tmp : ${tmp}`)
    console.log(`afterstack : ${stack}`)
    if (tmp == '') answer.push(str);
    else {
      const tmpStr = stack.join('');
      const idx = tmpStr.lastIndexOf('0') + 1;
      // console.log(idx);
      answer.push(tmpStr.substring(0, idx) + tmp + tmpStr.substring(idx));
    }
    // console.log();
  }
  return answer;
}
function find110(str, stack) {
  let tmp = '';
  // console.log(str, stack);
  for (let i = 0; i < str.length; i++) {
    const c = str.charAt(i);
    if (stack.length >= 2) {
      const b = stack.pop();
      const a = stack.pop();
      // console.log(`a:${a}, b:${b}, c:${c}`);
      if (a == '1' && b == '1' && c == '0') {
        tmp += '110';
        continue;
      }
      stack.push(a);
      stack.push(b);
    } // if
    stack.push(c);
    // console.log(stack);
  }
  return tmp;
}

// [ '1101', '100110110', '0110110111' ]
let s = ["1110", "100111100", "0111111010"];
console.log(solution(s));

이틀에 걸쳐서 푼 문제다.
처음에 풀때는 그냥 문제 그대로 과정 하나하나 구현하여 풀었다.
문자열에서 110을 잘라내고, 남은 문자열의 각 위치마다 잘라낸 110을 넣은 Set을 하나 만들고, 배열로 복사하여 정렬한 후 가장 앞의 요소를 answer에 push해서 답을 도출했다.
하지만 당연하게도 시간초과가 났다.

그 다음 다른사람의 풀이를 찾아 보았다.
내가 본 방법은 스택을 활용하는 방법이다.
먼저 문자열에서 110을 모두 찾아서 제거한다. 문자열을 처음부터 끝까지 돌면서, stack의 길이가 2보다 작다면, 그냥 stack에 해당 글자를 push. 아니라면 stack을 2번 pop해서 110을 이루는 지확인하고, 110이라면 tmp에 110을 더하고, 아니라면 다시 stack에 돌려놓는다.
2이상인 경우를 확인하는 이유는 그래야 3글자를 만들 수 있기 때문이다.
반복이 끝나면 남은 문자열 tmp를 return한다.

return한 문자열이 비었다면 str을 그대로 push한다.
그렇지 않다면 위치를 알맞게 넣어주어야한다.
그 방법은 뒤에서 0의 위치를 찾고, 해당 인덱스 이후에 tmp를 넣어준다.
왜냐하면 110이 모두 제거되었기 때문에 문자0앞에는 1이 연속적으로 2개이상 오지 못한다.
그러므로 0뒤에 남은 문자열을 넣었을 때 사전순으로 가장 앞에 오는 문자열을 만들 수 있다.

한번에 풀 수 있을 줄 알았는데 시간초과의 해결방법을 해결하지 못해 아쉬웠다.
추가로 마지막 0을 찾을때 처음에 반복문으로 했는데 lastIndexOf를 이용해 바로 찾을 수 있다.

📘 참고

https://velog.io/@longroadhome/프로그래머스-LV.3-110-옮기기-JS
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/String/lastIndexOf
https://joojaewoo.github.io/posts/110/