TIL 240531 - 알고리즘 코드카타 리뷰 - 햄버거 만들기

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/133502

프로그래머스

요약하자면, 어떤 배열이 주어졌을 때 배열에서 순차적으로 [1, 2, 3, 1] 을 추출한다. 최대로 많이 추출할 수 있는 개수를 구하는 문제이다.

ex)

[2, 1, 1, 2, 3, 1, 2, 3, 1] > 3번째부터 나타나는 [1, 2, 3, 1] 제거 > [2, 1, 2, 3, 1] 남음 > 2번째부터 나타나는 [1, 2, 3, 1] 제거 > [2] 남음 > 총 2번 추출 > 2 출력

 

2. 초기 코드

function solution(s) {
  let a = s.filter((i) => i==2).length;
  s = s.join("");
  let arr = "1231";
  while (s.includes(arr)) {
    s = s.replaceAll(arr, "");
  }
  let b = s.split("").filter((i) => i=="2").length;
  return (a-b);
}

 

배열을 문자열로 바꾼 뒤, 순회하며 "1231"을 모두 빈 문자열로 바꿔준다. 이 과정을 "1231"이 없을때까지 반복한다.

 

이렇게하면 되는줄 알았는데..아니었다.

배열이 [1, 1, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1] 일 경우, 한번에 모든 1, 2, 3, 1을 없애는것 보다, 처음 나타나는 1, 2, 3, 1을 없앤 뒤 나머지 1, 2, 3, 1을 없애는 것이 제일 많이 추출하는 방법이다.

 

그러니까, 모든 1, 2, 3, 1을 한번에 없애기보다는 순차적으로 하나씩 1, 2, 3, 1을 없애줘야 한다는 뜻.

그래서 replaceAll 대신 replace를 써봤다.

 

function solution(s) {
  let a = s.filter((i) => i==2).length;
  s = s.join("");
  let arr = "1231";
  while (s.includes(arr)) {
    s = s.replace(arr, "");
  }
  let b = s.split("").filter((i) => i=="2").length;
  return (a-b);
}

 

그런데, 테스트에서 주어지는 배열의 길이가 매우 길기 때문에, 시간 초과로 해결되지 못한 테스트들이 많았다....

배열을 여러번 순회하기 때문에 시간이 초과되는 것 같았다.

배열을 딱 한번만 순회하면서 순차적으로 추출할 방법이 있을까 고민하다가, 방법을 찾았다.

 

3. 최종 코드

function solution(s) {
  let answer = 0;
  const stack = [];
  
  for (i of s) {
      stack.push(i);
      
      if (stack.length >= 4) {
          const burger = stack.slice(-4).join("");
          
          if (burger === '1231') {
              stack.splice(-4);
              answer += 1;
          }
      }
  }
  
  return answer;
}

 

빈 스택에 배열 요소를 하나씩 집어넣는다.

스택의 길이가 4가 넘어가면 스택의 끝에 있는 4개의 요소가 1, 2, 3, 1인지 비교하여, 일치할 경우 스택의 끝 4개 요소 (1, 2, 3, 1)을 제거한다.

이 과정을 반복한다.

 

이렇게 하면 배열을 여러번 순회할 필요 없이 추출이 쉽게 가능하다.

 

순차적으로 배열 요소를 제거해야하는 문제 > 빈 스택에 하나씩 넣어보자....