[ 99클럽/미들러 ] 1일차 TIL : 햄버거 만들기

---

• 합류한 당일 문제가 날라올 줄 몰랐다. 어제 문제를 오늘 풀게 되었다. ㅎㅎ

---

문제 요약

1은 빵, 2는 야채, 3은 고기를 의미한다.
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≤ingredient≤1,000,000$

[ 프로그래머스 ]

• Java
• 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12945

---

풀이

• 완성된 햄버거는 배열에서 빼야하기 떄문에 추가, 삽입 등의 활동이 수월한 ArrayList를 사용했다.

1) 배열을 ArrayList를 재정의
2) 0부터 시작하여 1을 만날 경우, 해당 인덱스부터 +3까지 각각 2, 3, 1로 이뤄지는지 확인
- 그렇다면, remove를 이용하여, 햄버거 갯수 증가 및 해당 재료를 뺀 후, 다시 -3번째 부터 다시 탐색
- 그렇지 않다면, 탐색 index 값 증가

---

Code

import java.util.*;
class Solution {
    public int solution(int[] ingredient) {
        int answer = 0;
        ArrayList<Integer> ingreList = new ArrayList<>();
        for(int i=0;i<ingredient.length;i++) {
            ingreList.add(ingredient[i]);
        }
        int i=0;
        while (i < ingreList.size()) {
            if (i+3 >=ingreList.size())
                break;
            
            if (i>=0 && ingreList.get(i)==1 && ingreList.get(i+1)==2 && ingreList.get(i+2) == 3 && ingreList.get(i+3) == 1) {
                for(int j=0;j<4;j++) {
                    ingreList.remove(i);
                }
                i-=3;
                answer++;
                continue;
            }
            i++;
        }
        return answer;
    }
}

---

시도

1) i=0으로 돌아가기

탐색 결과 햄버거가 완성될 경우, 해당 재료를 뺀 후 0부터 다시 탐색을 시작하도록 구성해봤다.
이럴 경우, 시간 초과가 발생하게 된다.

2) 뺀 재료만큼만 앞으로 가기

아예 처음부터가 아닌 뺀 재료만큼 앞으로 즉, i-3만큼 앞으로 이동하여 다시 탐색하도록 하자. 햄버거는 4개의 재료로 이뤄져 있기 때문에, 빠진 재료의 다음 재료는 최대 -3번째 재료에게까지 영향을 미쳐 햄버거가 될 수도 있기 때문이다.

느낀점

처음부터 다시 탐색해야겠구나 생각만 했지만, 바로 이전꺼부터 다시 탐색하면 되는구나는 생각을 못 했다. 뭐든 기준이 중요하다는 생각이 들었다.