[프로그래머스] 햄버거 만들기 (C++)

문제

프로그래머스

풀이

이 문제는 빵, 야채, 고기, 빵 순으로 햄버거를 몇 개 만들 수 있는지 반환하는 문제이다.

즉,  1 >> 2 >> 3 >> 1 순서로 나오는 정수가 몇 개 있는지 찾으면 되는 문제이다.

 

한 가지 고려해야할 점은 햄버거가 만들어진다면 사용된 재료(숫자)들은 사라지고 밑에 깔려 있는 재료(숫자)들을 이용해서 햄버거를 만들 수 있다는 점이다.

 

예를들어, 빵, 야채, 빵, 야채, 고기, 빵, 고기, 빵 순서대로 있다면 만들 수 있는 햄버거의 갯수는 2개이다.

빵 (1), 야채 (2), 고기 (1)

1. 빵
2. 빵, 야채
3. 빵, 야채, 빵
4. 빵, 야채, 빵, 야채
5. 빵, 야채, 빵, 야채, 고기
6. 빵, 야채, 빵, 야채, 고기, 빵
7. 빵, 야채, 고기
8. 빵, 야채, 고기 빵

이렇게 해서 총 2개의 햄버거가 만들어진다.

 

난 스택을 활용하여 해당 문제를 풀이했다.

1. 각 재료들은 스택에 하나씩 쌓는다.
2. 스택의 크기가 4이상일 때, 즉 햄버거를 만들 수 있을 때, 빵이 들어온다면 햄버거를 만들 수 있는지 검사한다.
3. 햄버거를 만들 수 있다면 해당 재료들을 pop 한다.
4. 모든 재료를 탐색한 뒤, 만든 햄버거의 갯수를 반환한다.

#include <string>
#include <vector>

using namespace std;

vector<int> cook;

int AddCook(int num) {
	cook.push_back(num);
	int size = cook.size();
	if (num == 1 && size >= 4) {
		if (cook[size - 1] == 1 && cook[size - 2] == 3 && cook[size - 3] == 2 && cook[size - 4] == 1) {
			for (int i = 0; i < 4; i++) cook.pop_back();
			return 1;
		}
	}
	return 0;
}

int solution(vector<int> ingredient) {
	int answer = 0;

	for (int i = 0; i < ingredient.size(); i++) {
		int num = ingredient[i];
		answer += AddCook(num);
	}

	return answer;
}