햄버거 만들기
문제 설명
햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.
예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.
상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.
제한사항
- 1 ≤
ingredient의 길이 ≤ 1,000,000 ingredient의 원소는 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
- 문제 예시와 같습니다.
입출력 예 #2
- 상수가 포장할 수 있는 햄버거가 없습니다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
코드 구현
- Main
public class Main {
public static void main(String[] args) {
Solution sol = new Solution();
int n = 5;
int [] lost = {2,4};
int [] reserve = {1,3,5};
String [] keymap ={"ABACD", "BCEFD"};
String [] targets ={"ABCD","AABB"};
String [] keymap2 ={"AA"};
String [] targets2 ={"B"};
String s = "aukks";
String skip = "wbqd";
int index = 5;
int ingredient [] = {2, 1, 1, 2, 3, 1, 2, 3, 1};
System.out.println(sol.solution(ingredient));
}
}- 1차 시도
class Solution {
public int solution(int[] ingredient) {
String temp = "";
int answer = 0;
for(int i : ingredient)
temp += i;
while(temp.contains("1231")) {
temp = temp.replace("1231", "");
answer++;
}
System.out.println(answer);
return answer;
}
}트러블 슈팅
1차 시도에서는 단순하게 int형 배열을 temp라는 문자열에 문자열 형태로 저장한 이후 "1231"이라는 문자열을 temp에서 찾을 때마다 햄버거 생산 횟수를 증가시키고 찾은 문자열을 temp에서 제거하는 방식으로 코드를 제작했다.
하지만 이 방법에는 여러가지 문제점을 가지고 있다.
int 배열이 12, 31 과 같이 우리가 원하는 패턴(1, 2, 3, 1)과는 다른 잘못된 패턴도 햄버거 생산 횟수에 포함한다는 문제이다.
이러한 문제점으로 1차시도를 실패하게 되었다.
- 2차 시도
class Solution {
public int solution(int[] ingredient) {
List<Integer> list = Arrays.stream(ingredient).map(n -> n).boxed().collect(Collectors.toCollection(LinkedList::new));
int size =list.size()-3;
int check =1,answer=0;
while(check!=0) {
check = 0;
for (int i = 0; i < size; i++) {
if (list.get(i) == 1 && list.get(i + 1) == 2 && list.get(i + 2) == 3 && list.get(i + 3) == 1) {
list.remove(i);
list.remove(i);
list.remove(i);
list.remove(i);
check++;
if(i-3<0)
i=0;
else
i-=3;
size -= 4;
}
}
answer+=check;
}
System.out.println(answer);
return answer;
}
}트러블 슈팅
2차 시도에서는 Integer 참조 자료형 형태의 LinkedList 객체를 Arrays.stream을 이용해서 만들었다.
기능 자체는 구현에 성공하였지만 동작에 너무 많은 시간을 필요로 해서 실패했다.
- 3차 시도
class Solution {
public int solution(int[] ingredient) {
List<Integer> list = Arrays.stream(ingredient).map(n -> n).boxed().collect(Collectors.toCollection(LinkedList::new));
int size =list.size()-3;
int check =1,answer=0;
while(check!=0) {
check = 0;
for (int i = 0; i < size; i++) {
if (list.get(i) == 1 && list.get(i + 1) == 2 && list.get(i + 2) == 3 && list.get(i + 3) == 1) {
list.subList(i,i+4).clear();
check++;
i=(i-3<0)?0:i-3;
size -= 4;
}
}
answer+=check;
}
System.out.println(answer);
return answer;
}
}트러블 슈팅
3차 시도에서는 조금이라도 속도를 높이기 위해 remove 방식을 subList().clear을 이용해 한번에 처리하는 방식으로 수정하였지만 여전히 해결하지 못하였다.
- 4차 시도
import java.util.*;
class Solution {
public int solution(int[] ingredient) {
List<Integer> list = new ArrayList<>();
for (int i : ingredient) {
list.add(i);
}
int answer = 0;
int i = 0;
while (i < list.size() - 3) {
if (list.get(i) == 1 && list.get(i + 1) == 2 && list.get(i + 2) == 3 && list.get(i + 3) == 1) {
list.subList(i, i + 4).clear();
answer++;
i = Math.max(0, i - 4);
} else {
i++;
}
}
System.out.println(answer);
return answer;
}
}
해결
4차 시도에서는 기존에 사용하던 리스트의 특성에 대해 알아 보았다.
LinkedList와 ArrayList를 비교해 보니 리스트를 index 통해 접근하는 과정에서 LinkedList의 시간 복잡도는 O(n) 이지만 ArrayList는 O(1)이라는 사실과 삭제의 경우에는 LinkedList가 O(1), ArrayList는 O(n), 추가는 LinkedList는 O(1), ArrayList는 O(1)~O(n) 인 것을 알 수 있었다
현재 내 코드에서는 추가는 끝에서만 이루어 지기에 둘다 O(1)이고 삭제과 조회 작업의 비율이 1:4이기에 LinkedList보다 ArrayList가 더 합리적이고 성능을 올릴 수 있다고 판단하였고 실제 문제를 해결 했다.
Plus
