[프로그래머스][C++] 햄버거 만들기
문제
문제 링크
분석
빵(1), 야채(2), 고기(3)로 순서를 맞춰 햄버거를 만드는 문제입니다.
햄버거의 순서는 1, 2, 3, 1입니다.
순서는 바꿀 수 없고, 만들 때 사용된 재료를 제외하고, 나머지 재료를 이어서 조합할 수 있습니다.
풀이
재료에 대한 순서를 각 인덱스에서 관리하는 방법입니다.
#include <vector>
using namespace std;
int solution(vector<int> ingredient) {
int answer = 0;
// 재료의 순서를 저장할 배열
vector<int> hamburger;
// ingredient 순회
for(int e : ingredient)
{
// 재료를 저장
hamburger.push_back(e);
// 현재 재료가 4개 이상, 순서대로 준비되어 있는 경우
if (hamburger.size() >= 4 &&
hamburger[hamburger.size() - 4] == 1 &&
hamburger[hamburger.size() - 3] == 2 &&
hamburger[hamburger.size() - 2] == 3 &&
hamburger[hamburger.size() - 1] == 1)
{
// 재료 4개에 대해 마지막 요소 4개 제거
hamburger.erase(hamburger.end() - 4, hamburger.end());
++answer;
}
}
return answer;
}
ingredient를 순회하면서 재료들을 배열에 1개씩 저장하게 됩니다.
배열의 마지막 4개의 요소가 순서대로 1231로 저장되어있는지 확인하고, 순서대로 저장됐다면 해당 요소 4개를 제거하고, 만들 수 있는 햄버거의 개수를 1개 증가합니다.
재료의 순서를 하나의 값으로 합쳐서 관리하는 방법입니다.
#include <vector>
using namespace std;
int solution(vector<int> ingredient) {
int answer = 0;
// 재료의 순서를 저장할 배열
vector<int> hamburger{0};
// ingredient 순회
for (int e : ingredient)
{
// 빵+야채인 경우
if (hamburger.back() == 1 && e == 2)
{
hamburger.back() = 12;
}
// 빵+야채+고기인 경우
else if (hamburger.back() == 12 && e == 3)
{
hamburger.back() = 123;
}
// 빵+야채+고기+빵이며, 햄버거를 만들 수 있는 경우
else if (hamburger.back() == 123 && e == 1)
{
answer++;
// 현재 요소 제거
hamburger.pop_back();
}
else
{
// 새로운 인덱스에서 재료를 저장
hamburger.push_back(e);
}
}
return answer;
}
ingredient를 순회하면서 hamburger의 마지막 요소를 확인하고, 현재 ingredient의 요소가 필요한 요소인지 확인합니다.
만약 필요한 요소였다면 hamburger의 마지막 배열에 접근해 값을 바꾸어줍니다.
hamburger의 각 인덱스에는 재료에 대한 일종의 스택을 쌓는데, 재료에 대한 순서를 합쳐서 관리합니다.
성능 요약
재료에 대한 순서를 각 인덱스에서 관리한 성능입니다.
시간 복잡도는 $O(n)$입니다.
ingredient를 순회하는 반복문 $O(n)$hamburger.erase(hamburger.end() - 4, hamburger.end())로 요소를 제거 $O(4) \approx O(1)$- 요소를 제거하는 패턴이 계속 발생한다면 $O(n/4) \approx O(n)$
- $O(n) + O(n)$
공간 복잡도는 $O(n)$입니다.
- 모든 요소로 햄버거를 1개도 만들 수 없는 경우 $O(n)$
테스트 1 〉 통과 (0.01ms, 4.19MB)
테스트 2 〉 통과 (0.01ms, 4.11MB)
테스트 3 〉 통과 (3.96ms, 14.7MB)
테스트 4 〉 통과 (9.12ms, 27.7MB)
테스트 5 〉 통과 (11.31ms, 33.4MB)
테스트 6 〉 통과 (5.82ms, 19.7MB)
테스트 7 〉 통과 (8.31ms, 25.7MB)
테스트 8 〉 통과 (5.72ms, 20.4MB)
테스트 9 〉 통과 (4.74ms, 16.6MB)
테스트 10 〉 통과 (0.14ms, 4.18MB)
테스트 11 〉 통과 (3.22ms, 12.5MB)
테스트 12 〉 통과 (12.88ms, 38.8MB)
테스트 13 〉 통과 (0.01ms, 4.2MB)
테스트 14 〉 통과 (0.01ms, 4.16MB)
테스트 15 〉 통과 (0.01ms, 4.1MB)
테스트 16 〉 통과 (0.01ms, 3.58MB)
테스트 17 〉 통과 (0.01ms, 4.11MB)
테스트 18 〉 통과 (0.01ms, 4.21MB)
재료의 순서를 하나의 값으로 합쳐서 관리한 성능입니다.
시간 복잡도는 $O(n)$입니다.
ingredient를 순회하는 반복문 $O(n)$- $O(n)$
공간 복잡도는 $O(n)$입니다.
- 모든 요소로 햄버거를 1개도 만들 수 없는 경우 $O(n)$
테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (3.92ms, 13.7MB)
테스트 4 〉 통과 (9.75ms, 27.8MB)
테스트 5 〉 통과 (12.11ms, 33.6MB)
테스트 6 〉 통과 (6.71ms, 19.6MB)
테스트 7 〉 통과 (7.71ms, 23.6MB)
테스트 8 〉 통과 (5.95ms, 20.5MB)
테스트 9 〉 통과 (4.86ms, 16.5MB)
테스트 10 〉 통과 (0.14ms, 4.03MB)
테스트 11 〉 통과 (3.57ms, 12.6MB)
테스트 12 〉 통과 (13.88ms, 38.8MB)
테스트 13 〉 통과 (0.01ms, 3.68MB)
테스트 14 〉 통과 (0.01ms, 4.21MB)
테스트 15 〉 통과 (0.01ms, 3.68MB)
테스트 16 〉 통과 (0.01ms, 3.69MB)
테스트 17 〉 통과 (0.01ms, 4.2MB)
테스트 18 〉 통과 (0.01ms, 4.01MB)
댓글남기기