[프로그래머스 1단계] 햄버거 만들기 c++

문제 요약

 빵 – 야채 – 고기 - 빵

1-2-3-1 의 순서인 것이 몇 번 등장하는지 확인하기

이때 1-1-2-3-1-2-3-1 이라면 2번 등장

즉, 1-2-3-1이 등장하면 해당 부분을 제외하고 다시 확인해줘야한다.

 

예시 입출력

ingredient	result	설명
[2, 1, 1, 2, 3, 1, 2, 3, 1]	2	[2, 1, 1, 2, 3, 1, 2, 3, 1] -> [2, 1, 2, 3, 1]
[1, 3, 2, 1, 2, 1, 3, 1, 2]	0	조건에 해당하는 것이 존재하지 않음

 

내 코드 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int> ingredient) {
    int answer = 0;
    int i=0;
    int k=0;
   
while(1){
    if(i>ingredient.size()-3){
        i=0;
    }
    if(ingredient.size()<4){
        break;
    }
    if(k >ingredient.size())
    {
        break;
    }

   if (ingredient[i] == 1 && ingredient[i + 1] == 2 && ingredient[i + 2] == 3 && ingredient[i + 3] == 1) {
                ingredient.erase(ingredient.begin()+i, ingredient.begin()+i+4);
                answer++;
                k=0;
                i -= 2;
   }
    else{
        i++;
        k++;
    }
    
}
    return answer;
}

 

코드 풀이 : 

 if(i>ingredient.size()-3){
        i=0;
    }

만약 i가 ingredient.size()-3보다 커지면 햄버거가 완성될 수 없기에 다시 처음으로 돌림

 

해당 if문을 넣지 않으면 core dumped에 걸려버린다.

if(ingredient.size()<4){
        break;
    }

4보다 작은 벡터면 햄버거를 완성시킬 수 없기에 반복문을 나가게 했다.

if(k >ingredient.size())
    {
        break;
    }

k는 처음부터 끝까지 순회하는 건데 k를 둔 이유가 예시 2번처럼 하나도 맞는 것이 없을 때를 대비해서 두었다.

 

이처럼 break를 통해 나가게 하지 않는다면 시간 초과가 뜨게 된다.

if (ingredient[i] == 1 && ingredient[i + 1] == 2 && ingredient[i + 2] == 3 && ingredient[i + 3] == 1) {
                ingredient.erase(ingredient.begin()+i, ingredient.begin()+i+4);
                answer++;
                k=0;
                i -= 2;
   }

 

이 부분이 가장 핵심 로직이라고 할 수 있다. 처음엔 depth를 깊게 해서 if문을 작성하였는데 그냥 &&문을 이용해서 한 번에 처리하는 것과 같다는 것을 깨달아서 변경하였다. 따로 else문을 두는 것이 아니기 때문에 한 번에 작성하여도 되었다. 1-2-3-1이 있다면 답을 증가시켜주고 다시 k=0으로 돌려주고 i-=2;해서 지나쳤던 부분으로 다시 돌아가서 1-2-3-1을 제외하고 난 뒤의 벡터에서 조건에 맞는 부분이 있는지 확인해준다.

else{
        i++;
        k++;
    }

1-2-3-1이 아니라면 i와 k를 증가시켜서 위치를 앞으로 나아가게 한다.

 

어려움을 겪은 점 : 시간초과가 발생하여서 어려움을 겪었다. i-=2부분을 원래 i=0(처음부터 순회)하도록 했었는데 이는 시간 소모가 크다는 것을 알게 되었다. 어떻게 해결해야할 지 난항을 겪던 중, 처음부터 순회할 필요가 없을 것이라는 생각이 들었다. 바꿔주었더니 바로 시간 초과가 뜨지 않고 해결할 수 있었다.

 

모범 답안

#include <string>
#include <vector>
using namespace std;

int solution(vector<int> ingredient) {
    int answer = 0;
    vector<int> v = { -1 };
    for(int x : ingredient){
        if(v.back() == 1 && x == 2) v.back() = 12;
        else if(v.back() == 12 && x == 3) v.back() = 123;
        else if(v.back() == 123 && x == 1) answer++, v.pop_back();
        else v.push_back(x);
    }    

    return answer;
}

 

 

이렇게 하면 시간 초과 걱정도 없고 깔끔하게 해결할 수 있는게 너무 신기하다.. 

 

1. 만약 스택의 가장 위에 있는 요소가 1이고 현재 요소가 2인 경우, 패턴 "12"를 발견한 것이므로 스택의 가장 위 요소를 12로 바꾼다.

2. 만약 스택의 가장 위에 있는 요소가 12이고 현재 요소가 3인 경우, 패턴 "123"을 발견한 것이므로 스택의 가장 위 요소를 123으로 바꾼다.

3. 만약 스택의 가장 위에 있는 요소가 123이고 현재 요소가 1인 경우, 패턴 "1231"을 발견한 것이므로 패턴을 찾은 횟수를 증가시키고 스택에서 요소를 제거한다.

4. 그렇지 않은 경우, 현재 요소를 스택에 추가한다.

 

정답률 51% 문제