[JS] 햄버거 만들기

프로그래머스

문제 이해

재료는 1,2,3으로 제시되며 각각 빵, 야채, 고기를 의미한다.

즉 문제설명에 제시된 재료는 [2,1,1,2,3,1,2,3,1]이다. 2번째 인덱스부터 1,2,3,1이 구성되니 햄버거 하나가 완성되어 재료가 [2,1,2,3,1]이 되어 1번째 인덱스부터 또 1,2,3,1이 되어 두 번째 햄버거가 완성된다.

이 예시를 통해 알 수 있듯이 모든 1,2,3,1을 먼저 제거하는 것이 아니라, 제거한 후에 해당 위치에 또 다른 1,2,3,1이 만들어지면 그것을 먼저 없애야한다.

 

다른 예시를 살펴보자. [1,1,1,2,3,1,2,3,1,2,3,1]의 경우, 2번째와 8번째 인덱스에서 바로 총 2개의 햄버거가 만들어지는 것을 알 수 있는데, 이렇게 생각하면 일부만 정답일 것이다. 1번째에서 만들어진 햄버거를 제거하면 [1,1,2,3,1,2,3,1] 이 남고 1번째에 만들어진 새로운 햄버거가 두번째 햄버거가 되어야 한다. 이를 제거하면 [1,2,3,1]이 되고 총 3개의 햄버거가 만들어진다.

 

방법1

먼저 문자열의 `replace` 메소드가 생각났다. 찾는 동시에 제거를 할 수 있어 제격이라고 생각했다. 그래서 입력된 배열 자체를 `ingredient.toString()`으로 문자열로 바꾸었는데, 쉽표를 `replace`를 사용해 추가로 제거해야 하는 과정이 있어 비효율적인 것 같았다. (`burger = '1,2,3,1'`로 설정)

 

방법2

`join` 메소드를 사용해 다른 문장 부호가 없는 문자열로 바꾸었다. 이에 맞춰 `burger='1231'`로 변경해주었고, 쉼표를 제거과정을 없앨 수 있었다. 여기서 반복분에 대해 이야기해보자.

 

반복문은 for문과 while문 중 하나를 택해야할 필요는 없었다. 인덱스를 사용한 접근도 가능해보였고, `burger`를 포함하고 있는지를 사용한 while문도 가능해보였다. 나는 후자를 택했다.

function solution(ingredient) {
  let answer = 0;
  const burger = "1231";

  let stringIngredient = ingredient.join('');
  
  while (stringIngredient.includes(burger)) {
    stringIngredient = stringIngredient.replaceAll(burger,' ');
    
    for (const str of [...stringIngredient]) {
      if (str === ' '){
        answer++;
      }
    }
    stringIngredient = stringIngredient.replaceAll(' ','');
  }

  return answer;
}

 

위 과정은 `replaceAll` 메소드를 사용해서 반복문을 중첩했다. 이것도 비효율적으로 보였다. 또한 접근 방법도 맨 위에서 설명한 것과 다르다. `replaceAll`로 당장 보이는 햄버거를 제거해버리면 두 번째 예시처럼 3개를 만들 수 있는 경우도 2개밖에 만들지 못할 것이다.

 

방법3

`replace` 메소드를 사용해 가장 먼저 보이는 햄버거부터 제거하도록 바꾸었다.

function solution(ingredient) {
  var answer = 0;
  const burger = "1231";

  let stringIngredient = ingredient.join("");

  while (stringIngredient.includes(burger)) {
    stringIngredient = stringIngredient.replace(burger, "");

    answer++;
  }

  return answer;
}

이 방법은 당연히 성공할 줄 알았는데, 시간 초과로 실패했다. 이후 시간 초과를 다루기 위한 여정이 떠났고, 결론을 먼저 말하자면 나는 실패했다. 이 접근으로는 시간 초과를 해결할 수 없는 것 같다.

 

방법4

실패한 방법이지만 시간 초과 케이스가 줄어든 방법을 기록하려고 한다. while문에서 문자열 메소드 `includes`와 `replace`두 개를 사용한다. 문제를 해결하려면 `replace`를 해야하므로 하나를 없앤다면 `includes`를 없애기로 했다. 그래서 while문 조건을 아래와 같이 바꿨다.

  while (stringIngredient !== stringIngredient.replace(burger, "")) {
    stringIngredient = stringIngredient.replace(burger, "");

    answer++;
  }

 

그런데 결과가 동일한 `replace`를 두 번 사용하게 되어 이것도 한 단계 줄일 수 있을 것 같았다. 그래서 최종적으로 아래와 같은 코드를 얻었다.

function solution(ingredient) {
  var answer = 0;
  const burger = "1231";

  let stringIngredient = ingredient.join("");

  while (stringIngredient !== (tmp = stringIngredient.replace(burger, ""))) {
    stringIngredient = tmp;

    answer++;
  }

  return answer;
}

 

이 방법은 보기 불편해서 잘 사용하지 않았던 방법이다. 할당과 동시에 사용되므로 초보자가 정확히 사용하기에 어려울 것 같았다. 하지만 이번에 사용해보니 시간 문제를 해소해주는 것을 알 수 있었다.

 

방법5

마지막으로 다른 사람 코드를 찾아보았다.

function solution(ingredient) {
  // 다른 사람 풀이
  let answer = 0;
  const stack = [];
  
  for (let i = 0; i < ingredient.length; i++) {
    stack.push(ingredient[i]);
      
    if (stack.length >= 4) {
      const burger_ingredient = stack.slice(-4).join("");
          
      if (burger_ingredient === '1231') {
        stack.splice(-4);
        answer += 1;
      }
    }
  }
  
  return answer;
}

 

배열을 사용해 `splice`를 하면 시간 단축이 많이 되나보다. 이 코드를 문자열을 사용하는 것으로 바꿔서 `slice`나 `substring` 메소드를 사용해 보았는데, 여전히 시간 초과가 떴다.

 

---

이번 문제를 통해 같은 내용일지라도 메소드마다 계산 속도가 다르다는 것을 알 수 있었다. 사실 배열에 인덱스를 조절해가며 해결하려면 신경쓸 것이 많아질 것 같아 문자열을 사용한 건데, 이런 경험을 하게 되었다.