[프로그래머스] 햄버거 만들기

첫번째 풀이가 시간초과가 났다. 원인은 반복문 안의 indexOf()는 시간복잡도가 높음!

stack 자료구조를 사용해봄. 이 자료구조는 First In Last Out 마지막에 들어온게 가장 먼저 나가는 식. 이 자료구조를 선택한 이유는 순서대로 1231이 들어올때마다 로직이 돌아야 한다. 따라서 마지막에 어떻게 값이 들어오는지가 중요하기 때문에 stack을 사용. 마지막 4개의 값들을 체크해주기만 하면 된다.

 

풀이

// 첫번째 풀이 방법 : StringBuilder를 이용해 ingredient값을 append()
// -> while()문을 이용해 StringBuilder의 indexOf를 이용해 "1231"을 찾음
// -> 있으면 delete(index, index+4)해서 지워줌, answer++
// -> 무한반복 -> indexOf("1231") ==-1 break;
// 첫번째 풀이 실패 시간초과 났음 이유: 반복문 안에 indexOf()는 시간복잡도 높음

import java.util.*;

class Solution {
    public int solution(int[] ingredient) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        if(ingredient.length>3){
            //넣을 때 1231이 있으면 pop을 4번해주기
            for(int i=0;i<ingredient.length;i++){
                stack.push(ingredient[i]);
                if(stack.size()>3 &&
                    (stack.get(stack.size()-4)==1) &&
                    (stack.get(stack.size()-3)==2) &&
                    (stack.get(stack.size()-2)==3) &&
                    (stack.get(stack.size()-1)==1)){
                    for(int j=0;j<4;j++) {stack.pop();} 
                    answer++;
                }
            }
            return answer;
        }else return 0;
    }
}