[Java Script] 햄버거 만들기 풀이(프로그래머스_레벨1) with replace 시간복잡도 해결

[Java Script] 햄버거 만들기 풀이

프로그래머스_레벨1

 

 

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

프로그래머스

 

 

📌 문제

 

 

 

문제 설명

햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.

 

예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.

상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

 

 

제한사항

• 1 ≤ ingredient의 길이 ≤ 1,000,000
• ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미합니다.

입출력 예

ingredient	result
[2, 1, 1, 2, 3, 1, 2, 3, 1]	2
[1, 3, 2, 1, 2, 1, 3, 1, 2]	0

 

 

 

💡 문제풀이

 

1. 초기 접근 풀이_실패

시간초과로 몇가지 케이스에서 런타임에러가 났다.

원인을 찾기위해 확인해보니 replace로 인해 시간초과였다.

 

repalce는 순차적으로 돌면서 해당값을 찾고 다시 삭제 하기위해 순차적으로 하나하나 비교하기 때문에 시간복잡도가 O(n)으로 여기서 n은 문자열의 길이 이다.  

아래의 코드에서는 while 루프에서 replace 메서드를 계속 호출하고 있기 때문에, 최악의 경우 시간 복잡도는 O(n^2)가 될 수 있다. 왜냐하면 문자열에서 패턴을 찾아 제거한 후에도, 제거된 결과 문자열을 다시 처음부터 끝까지 훑어야 하기 때문입니다.

 

//1231 이 면 해당 요소 삭제 삭제한 배열에서 1231 이면 또 삭제 만약 없으면 리턴 0
function solution(ingredient) {
    var answer = 0;
    let buger = ingredient.join("");
    let regex = /1231/;
    
    while(true) {
        let check = buger.length;
        buger = buger.replace(regex, '');
        
        if(buger.length == check){ 
            return answer;
        }else{
            answer++;
        }
    }
    
    return answer;
}

 

 

그래서 시간복잡도를 줄이는 방법이 필요해서 초기 접근방법인 정규표현식의 접근방식에서 바꿔야했다. 

 

접근방식

오랜시간 고민해보고 했으나 도무지 감이 오지않아 여러가지의 풀이를 참고하다가 제일 합리적인거 같은 풀이를 해석해서 적용했다.

 

1. 스택을 활용하기로했다. 하나씩 넣어주고 그 길이가 4이상이 되면 그때부터 패턴과 비교해줄거다.

 

2. 이 방법이 왜 시간복잡도를 줄여주냐면, 맨앞에 있는 배열을 빼버리면 엔진은 앞에 있는 배열을 빼고 그 자리에 뒤에 있는 요소를 앞으로 옮겨주고를 배열의 길이만큼 반복을 한다. 그래서 새롭게 순차적으로 배열을 다시 넣어주고 패턴과 맞으면 뒤에서부터 하나씩 빼기위해 굳이 순차적으로 돌면서 새로운 배열에 넣어주면서 패턴과 비교할거다.

 

3. input 이라는 배열에 필요없어진 재료들도 쌓이기 때문에 뒤에서 부터 4자리만 비교해주기위해 slice로 4자리씩만 잘라서 비교해야한다.

function solution(ingredient) {
    let answer = 0;
    let input = [];
    let pattern = '1231';
    
    for(let i = 0; i < ingredient.length; i++) {
        input.push(ingredient[i]);
        if(input.length >= 4){
            let temp = input.slice(-4).join('');
            if(temp == pattern) {
                answer++;
                input.splice(-4);
            }
        }
    }
    return answer;
}

 

 

 

 

참고

햄버거 만들기