[프로그래머스,Java] Level1: 햄버거 만들기

 

문제분석

 

정해진 레시피가있습니다.  빵 - 야채 -고기 - 빵

 

상수는 재료가 떨어지는걸 보고,  빵 - 야채 -고기 -빵 패턴이 보이면 바로 제작합니다.

 

-> 이걸 구현만 해내시면됩니다.  하지만 최적화를 시켜야하는게 문제죠

 

 

First Try: replaceFirst 문법 사용하여 풀기

 

우선 ingredient의 원소를 모두 문자열로 받아씁니다.

 

EX) 211231231 

 

그리고 빵 - 야채 - 고기 - 빵 인  "1231" 패턴을 찾아서 빈칸으로 만들고(지우기) 햄버거 1개를 추가합니다.

replaceFirst는 맨 처음 '1231'패턴을 찾기만 하는 문법입니다.

 

이걸 햄버거가 더이상 안만들어질때까지 반복시킵니다.

 

 

--->  But,  효율성 오류

 

추측되는 이유,  replaceFirst 내부에서 O(n)만큼 계속 연산이걸려서 효율성에러가 나는것같다.

replaceFirst가 처음부터 탐색하여서 그런가싶다

 

 

Second Try: replaceFirst() 로직을 내가 새롭게 짜서 더욱 최적화시키기

 

요점은 이거다.  replaceFirst()가 계속 처음부터 탐색하는게 문제다.

 

그렇다면, 계속 처음부터가아닌,  이미 탐색한부분을 내가 조정해주면 된다.

 

해당 로직이다.  

 

재료를 하나씩 받아들이고난후,  재료가 4개 이상부터 조건을 검사한다.

 

지금 현재, 4개의 재료들로 버거를 만들수 있는가?  만들수있다면, 햄버거를 만들고 삭제

-> replaceFirst("1231",""); 과 동일한 기능이지만,  다른점은 다시 처음으로 돌아갈 필요가 없다는점이다.

 

 

전체풀이

import java.util.*;
class Solution {
    public int solution(int[] ingredient) {
        int answer = 0;
        
       StringBuilder sb = new StringBuilder();
        
      for(int n :ingredient){
          sb.append(n);
          
          if(sb.length()>3&&sb.substring(sb.length()-4).equals("1231")){
              answer++;
              sb.delete(sb.length()-4,sb.length());
          }
      }
        
        
        return answer;
    }
}

 

문제 이해난이도는 쉽지만,  최적화하는데 발목을 잡는문제 였다.