상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다.
예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.
상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.
| ingredient | result |
|---|---|
| [2, 1, 1, 2, 3, 1, 2, 3, 1] | 2 |
| [1, 3, 2, 1, 2, 1, 3, 1, 2] | 0 |
🤔생각해보기
배열을 돌면서 1,2,3,1이 완성되면 제거하고, 뒤에있는 값들을 앞으로 당겨 다시 체크하면 될 것 같다.
👩🏻💻코드 작성해보기
import java.util.*;
class Solution {
public int solution(int[] ingredient) {
int answer = 0;
List<Integer> li = new ArrayList<>();
for(int i :ingredient) {
li.add(i);
while(li.size() >= 4) {
int n = li.size();
if(!(li.get(n-1) == 1
&& li.get(n-2)==3
&& li.get(n-3) ==2
&& li.get(n-4)==1)) break;
for(int j=0; j<4; j++) {
li.remove(li.size() -1);
}
answer++;
}
}
return answer;
}
}💬설명해보기
배열을 순서가 있고, 가변 길이로 사용하기 위해 List컬렉션중 ArrayList를 사용했다.
ArraysList에 ingredient의 값을 하나씩 추가하면서 사이즈를 확인한다. (햄버거를 만들기 위한 첫번째 조건: 재료가 4개 필요)
햄버거를 만들기 위한 첫번째 조건이 되면, 뒤에서부터 1,3,2,1 순인지 확인한다.
순서까지 맞다면 리스트의 마지막값 제거를 4회 진행한다.
🎙️후기
처음에는 스트림으로 배열을 Stringbuilder에 문자열로 넣고, replace로 처리해주는 코드를 작성했다. 그러나 테스트 12번에서 시간초과로 통과하지 못했다. (12번 뿐 아니라 다른 테스트에서도 실행시간이 많이 소요되었다.) 문자열을 돌면 실행시간이 많이 소요되니, 배열 그 자체로(리스트나 스택사용...) 처리해야하는 것을 알게되었고 위와 같은 코드를 작성하게 되었다.
🤔❓ List 중 어느것이 가장 빠를까?
머릿속에 물음표가 떠다니기 시작해 List 컬렉션을 3개(ArraysList, Vector, LinkedList) 모두 적용시켜보았다.위와같은 결과가 나오는 이유를 찾아보니 ArrayList와 LinkedList의 접근방식의 차이 때문인 것 같다.
ArrayList는 배열의 구조를 가지고 있기 때문에, 인덱스를 통해 바로 값을 가져올 수 있다.
반면 LinkedList는 이중연결리스트의 구조를 가지고 있기 때문에 특정 인덱스에 도달하기 위해서는 앞/뒤에서부터 해당 인덱스까지 순차적으로 접근해야 한다.
접근방식의 차이로 ArrayList가 LinkedList보다 빠른 속도를 가질 수 있었던 것 같다. (절대적으로 ArrayList가 가장 빠른것은 아니며, 사용방식에 따라 다르다. )
🙇🏻♀️
ArrayList와 LinkedList의 차이, 선택하기 - 그냥 그냥 블로그
(Java)ArrayList vs LinkedList 시간 복잡도 - 당근케잌
