문제
https://school.programmers.co.kr/learn/courses/30/lessons/133502
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
재료에 대한 번호가 주어졌을때, 햄버거에 대한 쌍으로 쌓여서 만들 수 있는 개수를 구하는 문제이다.
재료에 대해서 쌓는다고 적혀 있어서 바로 스택을 사용해야겠다는 생각을 했다.
빵이면서, 햄버거를 만들 수 있는 개수가 스택에 있다면
쌍을 모두 꺼내서 햄버거를 만들 수 있는지 확인해보면 된다.
첫번째 풀이
1. 스택을 선언한다.
2. 현재 스택에 저장되어 있는 재료의 개수가 4개 이상이고, 제일 상위에 있는 재료가 빵이라면
2-1. 4개의 재료를 모두 꺼내서 쌍이 되는지 확인하고, 쌍이 되지 않는다면 다시 넣는다.
2-2. 4개의 재료를 모두 꺼냈을 때, 햄버거를 만들 수 있다면, 개수를 센다.
두번째 풀이
배열 + 인덱스 연산으로 풀이
1. 재료를 담을 배열을 만든다.
2. 현재 배열에 저장되어 있는 재료의 개수가 4개 이상이고, 제일 상위에 있는 재료가 빵이라면
2-1. 4개의 재료를 인덱스로 접근해서 햄버거 쌍이 되는지 확인하고 햄버거를 만들 수 있다면 개수를 세고 인덱스를 4를 감소시킨다.
소스코드
import java.util.ArrayDeque;
class Solution {
final int BREAD = 1;
final int VEGETABLE = 2;
final int MEAT = 3;
final int PAIR_NUMBER = 4;
public int solution(int[] ingredient) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int answer = 0;
for (int ingre : ingredient) {
stack.addFirst(ingre);
if (stack.size() >= PAIR_NUMBER && stack.peekFirst() == BREAD) {
int fourth = stack.removeFirst();
int third = stack.removeFirst();
int second = stack.removeFirst();
int first = stack.removeFirst();
if (first != BREAD || second != VEGETABLE || third != MEAT || fourth != BREAD) {
stack.addFirst(first);
stack.addFirst(second);
stack.addFirst(third);
stack.addFirst(fourth);
continue;
}
answer++;
}
}
return answer;
}
}
class Solution {
final int BREAD = 1;
final int VEGETABLE = 2;
final int MEAT = 3;
final int PAIR_NUMBER = 4;
public int solution(int[] ingredient) {
int[] stack = new int[ingredient.length];
int answer = 0;
int idx = 0;
for (int ingre : ingredient) {
stack[idx++] = ingre;
if (idx >= PAIR_NUMBER && stack[idx - 1] == BREAD && stack[idx - 2] == MEAT && stack[idx - 3] == VEGETABLE && stack[idx - 4] == BREAD) {
idx -= PAIR_NUMBER;
answer++;
}
}
return answer;
}
}
실행결과


성능개선
| 구분 | 평균 실행 시간(ms) | 평균 메모리 사용량(MB) |
| 스택 풀이 | 27.77 | 96.77 |
| 배열 풀이 | 5.52 | 94.78 |
| 개선 | 80.1% 향상 | 2.1% 감소 |
'Problem Solving > Programmers' 카테고리의 다른 글
| [Programmers] 제일 작은 수 제거하기 - Java (0) | 2025.08.02 |
|---|---|
| [Programmers] 두 개 뽑아서 더하기 - Java (0) | 2025.08.01 |
| [Programmers] 개인정보 수집 유효기간 - Java (0) | 2025.07.30 |
| [Programmers] 내적 - Java (0) | 2025.07.29 |
| [Programmers] 큰 수 만들기 - Java (0) | 2025.07.28 |