프로그래머스) 햄버거 만들기 Lv1

햄버거를 순서대로 뽑아내는 문제입니다!

 

빵 : 1, 야채 : 2, 고기 : 3 

 

위 조건으로 1231 숫자를 최대로 뽑아낼 수 있는 방법을 구하는 코딩테스트 문제!

 

처음에는 무작위로 주어지는 int 배열을 String 하나의 문자로 만든 뒤

indexOf 를 통해 "1231" 문자가 없을 때까지("1231" 이 포함이면 -1 을 뽑음) while 문을 돌렸다

-> while(조건문) () 안의 조건이 거짓이 될 때까지 반복하는 반복문이다.(기본 문법인데 가끔 헷갈려서 설명추가;;)

 

테스트케이스 실행시에는 너무 잘되는데,

문제를 제출할 때 몇몇 캐이스가 시간초과가 떠버린다...

import java.util.*;

class Solution {
    public int solution(int[] ingredient) {
        int answer = 0;

        String checkBurger = Arrays.toString(ingredient).replaceAll(", ", "");
        
        while(checkBurger.indexOf("1231") > 0){
            answer++;
            checkBurger = checkBurger.replaceFirst("1231", "");
        }
        
        return answer;
    }
}

 

확인해보니 매개변수의 범위가 어마무시했다... (1 ≤ ingredient의 길이 ≤ 1,000,000)

ingredient의 길이가 길어질수록 변수를 String 으로 변환해주는 과정에서 시간을 많이 잡아먹혀서 시간초과가 발생한 것!

 

여기저기 정보를 찾아보다가 StringBuilder 를 사용하는 한 답변자를 보고 참고하여 문제를 풀었다

역시 세상은 넓고 천재들은 많다...

 

 

 

---

정답

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

 

 

출처

오월의 코딩일지 - https://programmer-may.tistory.com/154

프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/133502