728x90
반응형
SMALL
문제 설명
햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.
예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 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
- 상수가 포장할 수 있는 햄버거가 없습니다.
package LV1;
import java.util.Stack;
public class H133502 {
public int solution(int[] ingredient) {
// 함버거 재료 순서
int[] burger = {1, 2, 3, 1};
// 현재 맞춰야 하는 재로
int answer = 0;
// 완성된 햄버거 수
int count = 0;
// 재료를 담을 스택 생성
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < ingredient.length; i++) {
// 현재 재로가 맞춰야 하는 재료와 같으면
if (burger[answer] == ingredient[i]) {
// 재료를 스택에 넣고
stack.push(ingredient[i]);
// 다음에 맞춰야 하는 재료로 answer를 이동
answer = (answer + 1) % 4;
} else {
// 현재 재료가 맞춰야하는 재료와 다르면 스택을 비움
while (!stack.empty()) {
stack.pop();
}
// 현재 재료가 빵(1)이면 다시 스택에 넣고 햄버거 만드는 것을 시작
if (ingredient[i] == 1) {
stack.push(ingredient[i]);
}
// 맞춰야 하는 재료 answer를 빵(1)으로 초기화
answer = 1;
}
// 재료 스택이 4개가 되면 햄버거 하나 완성~
if (stack.size() == 4) {
// 햄버거 카운트를 증가시키고
count++;
// 스택을 비운다.
while (!stack.empty()) {
stack.pop();
}
// 맞춰야 하는 재료 인덱스를 빵(1)로 초기화
answer = 0;
}
}
// 완성된 햄버거 수로 반환
return count;
}
}
테스트 1입력값 〉[2, 1, 1, 2, 3, 1, 2, 3, 1]
기댓값 〉2
실행 결과 〉실행한 결괏값 1이 기댓값 2과 다릅니다.
테스트 2입력값 〉[1, 3, 2, 1, 2, 1, 3, 1, 2]
기댓값 〉0
실행 결과 〉테스트를 통과하였습니다.
실패 ㅠㅠㅠ
순서가 아래에서부터 위로 쌓이기 때문에 재료가 쌓이는 순서도 반대로 되어야 하는데 실수…ㅠ
또한, 스택이 비워져서 새로 시작할 때 마다 다음 재료의 인덱스를 초기화하기!!
package LV1;
import java.util.Stack;
public class H133502 {
public int solution(int[] ingredient) {
// 햄버거 재료 순서를 반대로(위에서 아래로)
int[] burger = {1, 3, 2, 1};
// 완성된 햄버거 수
int count = 0;
// 재료를 담을 스택 생성
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < ingredient.length; i++) {
// 스택이 비어있거나 스택의 top 재료가 다음에 필요한 재료라면 스택에 추가
if (stack.isEmpty() || stack.peek() == burger[stack.size() % 4]) {
stack.push(ingredient[i]);
} else {
// 아니라면 스택을 비우고 새로 시작
stack.clear();
if (ingredient[i] == 1) {
stack.push(ingredient[i]);
}
}
// 스택의 크기가 4가 되면 햄버거가 완성된 것이므로 카운트를 올리고 스택을 비움
if (stack.size() == 4) {
count++;
stack.clear();
}
}
return count;
}
}
테스트 1
입력값 〉 [2, 1, 1, 2, 3, 1, 2, 3, 1]
기댓값 〉 2
실행 결과 〉 실행한 결괏값 0이 기댓값 2과 다릅니다.
테스트 2
입력값 〉 [1, 3, 2, 1, 2, 1, 3, 1, 2]
기댓값 〉 0
실행 결과 〉 테스트를 통과하였습니다.
햄버거는 아래에서부터 위로 빵, 야채, 고기, 빵 순으로 쌓인다. 따라서 빵이 추가되었을 때 그 다음 재료가 야채가 아니면 새로운 햄버거로 간주하고 새로 빵을 쌓아야 한다.
package LV1;
import java.util.Stack;
public class H133502 {
public int solution(int[] ingredient) {
// 햄버거 재료 순서를 반대로(위에서 아래로)
int[] burger = {1, 2, 3, 1};
// 완성된 햄버거 수
int count = 0;
// 재료를 담을 스택 생성
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < ingredient.length; i++) {
// 스택이 비어있거나 스택의 top 재료가 다음에 필요한 재료라면 스택에 추가
if (stack.isEmpty() || stack.peek() == burger[stack.size() % 4]) {
stack.push(ingredient[i]);
} else {
// 아니라면 스택을 비우고 새로 시작
stack.clear();
if (ingredient[i] == 1) {
stack.push(ingredient[i]);
}
}
// 스택의 크기가 4가 되면 햄버거가 완성된 것이므로 카운트를 올리고 스택을 비웁니다.
if (stack.size() == 4) {
count++;
stack.clear();
}
}
return count;
}
}
테스트 1
입력값 〉 [2, 1, 1, 2, 3, 1, 2, 3, 1]
기댓값 〉 2
실행 결과 〉 실행한 결괏값 0이 기댓값 2과 다릅니다.
테스트 2
입력값 〉 [1, 3, 2, 1, 2, 1, 3, 1, 2]
기댓값 〉 0
실행 결과 〉 테스트를 통과하였습니다.
스택의 최상단에 있는 재료와 현재 재료를 비교하는 조건을 잘못 작성….. 잘못된 코드의 경우, 스택의 최상단에 있는 재료가 이전 햄버거의 재료와 같은 경우에만 스택에 현재 재료를 추가
package LV1;
import java.util.Stack;
public class H133502 {
public int solution(int[] ingredient) {
int[] burger = {1, 2, 3, 1}; // 햄버거 재료 순서를 반대로(위에서 아래로)
int count = 0; // 완성된 햄버거 수
Stack<Integer> stack = new Stack<>(); // 재료를 담을 스택 생성
for (int i = 0; i < ingredient.length; i++) {
// 현재 재료가 햄버거 재료 순서를 따르는 경우에만 스택에 추가
if (stack.size() < 4 && ingredient[i] == burger[stack.size()]) {
stack.push(ingredient[i]);
if (stack.size() == 4) { // 스택의 크기가 4가 되면 햄버거 완성
count++; // 햄버거 수 증가
stack.clear(); // 스택 비우기
}
} else {
stack.clear(); // 스택 비우기
if (ingredient[i] == 1) { // 빵인 경우 새로운 햄버거 시작
stack.push(ingredient[i]);
}
}
}
return count; // 완성된 햄버거 수 반환
}
}
테스트 1
입력값 〉 [2, 1, 1, 2, 3, 1, 2, 3, 1]
기댓값 〉 2
실행 결과 〉 실행한 결괏값 1이 기댓값 2과 다릅니다.
테스트 2
입력값 〉 [1, 3, 2, 1, 2, 1, 3, 1, 2]
기댓값 〉 0
실행 결과 〉 테스트를 통과하였습니다.
조건을 정확히 반영하지 못한듯..
import java.util.*;
public class Solution {
public int solution(int[] ingredient) {
Queue<Integer> queue = new LinkedList<>();
int count = 0;
for (int i : ingredient) {
queue.add(i);
if (queue.size() == 4) {
if (queue.poll() == 1 && queue.poll() == 2 && queue.poll() == 3 && queue.peek() == 1) {
count++;
}
}
}
return count;
}
}
LinkedList로 바꾸기..!!!
- **Queue**를 사용하여 재료를 순서대로 추가하고, 큐의 크기가 4가 되면 맨 앞부터 재료를 꺼내어 빵, 야채, 고기, 빵 순서인지 확인
- 이 순서에 맞으면 햄버거를 완성했다고 판단하고 카운트를 증가시킵니다. 만약 순서가 맞지 않으면 빵이 나올 때까지 재료를 꺼내기
테스트 1
입력값 〉 [2, 1, 1, 2, 3, 1, 2, 3, 1]
기댓값 〉 2
실행 결과 〉 실행한 결괏값 1이 기댓값 2과 다릅니다.
테스트 2
입력값 〉 [1, 3, 2, 1, 2, 1, 3, 1, 2]
기댓값 〉 0
실행 결과 〉 테스트를 통과하였습니다.
어디가 문제인 건가………. 재료 배열에서 가능한 최대한 많은 햄버거를 만드는 것 이 부분인거 같아 다시 풀어보자 ㅠㅠ
public class Solution {
public int solution(int[] ingredient) {
int count = 0;
int i = 0;
while (i < ingredient.length - 3) {
if (ingredient[i] == 1 && ingredient[i + 1] == 2 && ingredient[i + 2] == 3 && ingredient[i + 3] == 1) {
count++;
i += 4;
} else {
i++;
}
}
return count;
}
}
- 재료 배열을 순회하면서 가능한 햄버거를 만드는 것을 시도합니다. 만약 햄버거를 만들 수 있다면, 카운트를 증가시키고 인덱스를 4 증가시켜 다음 재료를 확인
- 만약 햄버거를 만들 수 없다면, 인덱스만 1 증가
테스트 1
입력값 〉 [2, 1, 1, 2, 3, 1, 2, 3, 1]
기댓값 〉 2
실행 결과 〉 실행한 결괏값 1이 기댓값 2과 다릅니다.
테스트 2
입력값 〉 [1, 3, 2, 1, 2, 1, 3, 1, 2]
기댓값 〉 0
실행 결과 〉 테스트를 통과하였습니다.
햄버거를 만들 때 재료 순서를 보다 유연하게 확인해야한다.
현재의 로직은 재료가 정확하게 [빵, 야채, 고기, 빵] 순서로 쌓여있을 때만 햄버거로 인식
빵-야채-고기-빵 순서로 쌓여 있는 경우 어디서든 햄버거로 인식해야 한다. 즉, 재료 중간에 다른 재료가 끼어있더라도 해당 재료들로 햄버거를 만들 수 있어야 한다.
public class Solution {
public int solution(int[] ingredient) {
int count = 0;
int pointer = 0;
for(int i = 0; i < ingredient.length; i++) {
if(ingredient[i] == 1 && pointer == 0) pointer++;
else if(ingredient[i] == 2 && pointer == 1) pointer++;
else if(ingredient[i] == 3 && pointer == 2) pointer++;
else if(ingredient[i] == 1 && pointer == 3) {
pointer = 1;
count++;
} else if(ingredient[i] == 1) {
pointer = 1;
} else {
pointer = 0;
}
}
return count;
}
}
테스트 1 〉 통과 (0.02ms, 78.7MB)
테스트 2 〉 실패 (0.02ms, 74.2MB)
테스트 3 〉 실패 (9.71ms, 100MB)
테스트 4 〉 실패 (10.37ms, 115MB)
테스트 5 〉 실패 (14.19ms, 138MB)
테스트 6 〉 실패 (7.67ms, 91.1MB)
테스트 7 〉 실패 (9.30ms, 108MB)
테스트 8 〉 실패 (8.84ms, 105MB)
테스트 9 〉 실패 (10.68ms, 99MB)
테스트 10 〉 실패 (0.40ms, 74.5MB)
테스트 11 〉 실패 (8.08ms, 90.3MB)
테스트 12 〉 실패 (12.87ms, 132MB)
테스트 13 〉 통과 (0.01ms, 74.7MB)
테스트 14 〉 통과 (0.02ms, 74.9MB)
테스트 15 〉 통과 (0.03ms, 75MB)
테스트 16 〉 통과 (0.01ms, 81.2MB)
테스트 17 〉 통과 (0.03ms, 74.6MB)
테스트 18 〉 실패 (0.02ms, 74.5MB)
흐힝…
덱(Deque)을 이용해 문제를 해결할 수 있다. 덱은 스택과 큐의 기능을 모두 가진 자료구조로서, 양방향에서 데이터를 처리할 수 있다.
LinkedList는 덱의 기능과 인덱스를 사용한 요소 접근이 가능
완성코드
package LV1;
import java.util.LinkedList;
/*
햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다.
함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고,
상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다.
상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다.
상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며,
재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.
예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때,
상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때,
두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.
상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때,
상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.
*/
public class H133502 {
public int solution(int[] ingredient) {
// 재료를 담을 LinkedList(Deque)를 생성
LinkedList<Integer> deque = new LinkedList<>();
// 완성된 햄버거의 개수를 카운트하는 변수를 선언
int count = 0;
// 입력받은 모든 재료에 대해 순회
for (int i : ingredient) {
// 재료를 Deque의 맨 끝에 추가
deque.offerLast(i);
// Deque에 4개 이상의 재료가 있다면, 햄버거가 만들어질 수 있는지 검사
while (deque.size() >= 4) {
int size = deque.size();
// 최근에 추가된 4개의 재료가 "빵-야채-고기-빵" 순서인지 확인
if (deque.get(size - 4) == 1 && deque.get(size - 3) == 2 && deque.get(size - 2) == 3 && deque.get(size - 1) == 1) {
// "빵-야채-고기-빵" 순서라면, 햄버거를 만들고 해당 재료를 Deque에서 제거
for (int j = 0; j < 4; j++)
deque.pollLast();
// 햄버거의 개수를 증가시킴
count++;
} else {
// "빵-야채-고기-빵" 순서가 아니라면, 더 이상 재료를 제거하지 않고 검사를 멈춘다.
break;
}
}
}
// 완성된 햄버거의 개수를 반환
return count;
}
}
드디어 완성..!!!
- 변수 명명: **i**라는 변수 이름은 일반적으로 for 반복문의 인덱스에 사용된다. 여기서는 각각의 재료를 나타내므로, **i**보다는 **item**이나 ingredient 같은 의미 있는 이름을 사용하는 것이 좋다.
- Deque의 사용: **LinkedList**를 사용하여 Deque를 구현. **LinkedList**는 양쪽 끝에서의 추가 및 삭제가 O(1)이므로, 이 문제에 적합하다.
- 조건문 최적화: **while**문 안의 조건문에서 **deque.get(size - n)**을 반복해서 사용하고 있다. 이는 코드를 다소 복잡하게 만든다. 또한, 이 조건문은 **while**문이 반복될 때마다 같은 연산을 반복하게 된다. 아래와 같이 한 번만 계산하도록 최적화할 수 있다.
while (deque.size() >= 4) {
int fourth = deque.get(size - 4);
int third = deque.get(size - 3);
int second = deque.get(size - 2);
int first = deque.get(size - 1);
if (fourth == 1 && third == 2 && second == 3 && first == 1) {
// ...
} else {
// ...
}
}
- 함수 분리: 현재 solution 함수는 많은 일을 하고 있다. 햄버거를 만드는 로직을 별도의 함수로 분리하면 코드를 더욱 깔끔하게 만들 수 있다.
- 주석: 주석이 코드를 이해하는 데 매우 도움이 된다. 다만, 주석을 너무 많이 사용하면 오히려 코드를 읽기 어려울 수 있으므로 적절히 사용하는 것이 중요하다. 코드 자체가 명확하게 작성되어 있다면, 주석 없이도 이해할 수 있어야 한다.
- 매직 넘버: 코드 내에서 1, 2, 3 등의 숫자는 햄버거의 재료를 나타내는 "매직 넘버"입니다. 이러한 값들을 상수로 선언하면 코드의 가독성을 향상시킬 수 있다. 예를 들어:
final int BUN = 1;
final int VEGETABLE = 2;
final int MEAT = 3;
이렇게 상수를 사용하면, **if (fourth == BUN && third == VEGETABLE && second == MEAT && first == BUN)**처럼 명확한 코드를 작성할 수 있다.
728x90
반응형
LIST
'알고리즘 > 프로그래머스 JAVA LV.1' 카테고리의 다른 글
| 성격 유형 검사하기 (0) | 2023.05.23 |
|---|---|
| 개인정보 수집 유효기간 (0) | 2023.05.22 |
| 바탕화면 정리 (0) | 2023.05.17 |
| 숫자 짝꿍 (0) | 2023.05.17 |
| 크레인 인형뽑기 게임 (0) | 2023.05.17 |