[CodeKata] 프로그래머스(Lv3) : 110 옮기기

 

🥋 Oooth More!! (Level 3) 

 

 

 

🧮 풀이

110을 찾은 뒤, 이보다 큰 111이 있는 경우 이를 대치하면 된다고 생각했다.

또한, 대치된 110의 인덱스를 저장해서 다음 110을 찾을 때 해당 위치를 제외하려고 했으나, 복잡한 로직으로 시간초과가 발생하게 되었다.

 

 

 

🖇 리뷰

stack을 이용해 110들을 저장하고, 남은 값들 중 가장 끝에 있는 0 뒤로 이를 붙이면 되는 생각보다 쉬운 문제였다.

const answer = [];
function solution(s) {
  for (let t = 0; t < s.length; t++) {
    let str = s[t]
    let stack = [];
    let tmp = find110(str, stack);
    if (tmp == '') answer.push(str);
    else {
      const tmpStr = stack.join('');
      const idx = tmpStr.lastIndexOf('0') + 1;
      answer.push(tmpStr.substring(0, idx) + tmp + tmpStr.substring(idx));
    }
  }
  return answer;
}
function find110(str, stack) {
  let tmp = '';
  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();
      if (a == '1' && b == '1' && c == '0') {
        tmp += '110';
        continue;
      }
      stack.push(a);
      stack.push(b);
    }
    stack.push(c);
  }
  return tmp;
}

* 출처 : https://intrepidgeeks.com/tutorial/mobile-10javascript-programmers-110

 

1. find110() 함수

• 인자는 str(현재 문자열), stack(스택배열) 2개를 받는다.
• tmp는 찾은 110들을 저장하는 문자열이다.
• str를 순회하며 c(현재문자)와 stack의 가장 최근 2개 문자(a,b)를 확인한다. 이 셋이 110이면 tmp에 110을 더하고 다음 단계로 바로 넘어간다.
• 110이 아니라면 다음 순회로 정상적으로 넘어가야 한다. stack에 빼온 반대의 순서로, a, b, c를 차례로 넣어준다.
• 최종적으로, 우리가 찾은 110들을 가진 문자열 tmp를 반환한다.

 

2. solution() 풀이

• s 문자열 배열을 순회한다. str은 현재 문자열, stack은 스택배열이다.
• tmp는 find110() 함수의 반환값이다. 또한, stack 배열을 인자로 넘겨 참조했기 때문에, 여기엔 str에서 110들을 제외한 나머지 문자들이 들어가있다.
• tmp가 빈 문자열이라면 110이 없는 경우로, 이 땐 str 자체를 answer에 넣어주면 된다.
• 아니라면, 우선 stack의 문자들을 join() 한다. 그리고, 여기서 마지막 0의 위치를 lastIndexOf()로 찾고, 바로 다음 인덱스인 idx를 선언한다. (여기가, tmp가 들어갈 위치)
• str에서 idx에 tmp가 들어간 문자열을 최종적으로 answer에 넣어준다.