[250205 TIL] 햄버거 만들기 드디어 해결.. | 짐벌락 현상

1️⃣ 알고리즘 코드카타

[햄버거 만들기]
https://school.programmers.co.kr/learn/courses/30/lessons/161989

🤖 AI 피드백

1. stack을 활용하여 불필요한 if문 없이 마지막 4개 요소를 빠르게 비교 후 제거

2. 불필요한 for 루프 제거

3. 인덱스를 사용하기보다 stack을 활용하여 명확한 패턴 매칭

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(vector<int> ingredients) {
    int answer = 0;
    stack<int> s;

    for (int ing : ingredients) {
        s.push(ing);
        
        if (s.size() >= 4) {
            int a = s.top(); s.pop();
            int b = s.top(); s.pop();
            int c = s.top(); s.pop();
            int d = s.top(); s.pop();

            if (d == 1 && c == 2 && b == 3 && a == 1) {
                ++answer; // 햄버거 개수 증가
            } else {
                // 패턴이 아니면 다시 스택에 넣기
                s.push(d);
                s.push(c);
                s.push(b);
                s.push(a);
            }
        }
    }

    return answer;
}

 

💭 코드카타 회고

처음에는 문자열로 풀어보다가 시간초과 떴다.

 

문자열에서 erase를 사용해서인가 싶어

중간 삽입/삭제가 용이한 연결리스트로 해보았지만 또 시간초과..

 

결국 gpt에게 시간초과의 이유를 물어보고 스택이나 벡터를 추천받아

스택으로 풀어보아서 겨우 통과할 수 있었다.

 

근데 그 스택도 인덱스를 써서 원소에 접근해야할 것 같아서

벡터를 스택처럼 사용했더니 비효율적인 풀이었다니..

그래도 풀이가 안 떠오른 덕분에 여러 자료구조를 경험해볼 수 있었다..하하..
확실히 자료구조를 많이 안 써봤다보니
이번 문제를 통해 자료구조의 활용면에서의 취약함을 많이 느꼈다.

❗NewKnowlodge
▪️중간 삽입/삭제가 있을 때 인풋 범위가 방대하다면
     스택으로 마지막 원소를 삭제하는 것이 빠름(erase는 성능이 좋지 않다!)

문제 접근은 맞으나 시간 초과가 뜬 풀이

🔻연결리스트

int humberger = 0;

list<int> lst(ingredients.begin(), ingredients.end());

for(auto it = lst.begin(); it != lst.end(); ++it)
{
    if(*it == 1)
    {
        if(*next(it, 1) == 2)
        {
            if(*next(it, 2) == 3)
            {
                if(*next(it, 3) == 1)
                {
                    it = lst.erase(it, next(it, 4));
                    ++answer;
                    if(distance(lst.begin(), it) <= 4)
                    {
                        it = prev(lst.begin(), 1);
                    }

                    else
                        advance(it, -3);
                }
            }
        }      
    }
}

🔻 문자열

string sIngredients = "";
for(int ingredient : ingredients)
{
    sIngredients+=to_string(ingredient);
}

while(1)
{
    auto it = sIngredients.find("1231");
    if(it != string::npos)
    {
        sIngredients.replace(it, 4, "");
        ++answer;
    }
    else
    {
        break;
    }
}

 

2️⃣ 추가 공부

🔹짐벌락 현상

정의

3D 공간에서 오일러 각(Euler Angles) 기반 회전을 사용할 때 발생하는 문제

즉, 특정한 회전이 겹쳐서 하나의 축이 없어지고, 더 이상 원하는 방향으로 회전할 수 없게 되는 문제

❓오일러각
3개의 축에 대해 각각 회전을 나누어 적용(종속 관계)

https://daekyoulibrary.tistory.com/entry/%EA%B2%8C%EC%9E%84-%EC%88%98%ED%95%99-18-%EC%98%A4%EC%9D%BC%EB%9F%AC-%EA%B0%81Euler-angle

 

발생 이유

1. 오일러 각 기반 회전 사용

    FRotator -> 오일러 각 기반

 

2. Yaw, Pitch, Roll 순서의 문제

    오일러 각의 회전 순서는 정해져 있으며,

    특정 순서에서 두 축이 동일한 평면상에 놓이면서 회전이 제한됨.

 

3. 연속적인 회전 적용 시 비직관적인 결과 발생

    오일러 각 회전을 연속적으로 적용하면 축이 의도한 방향과 다르게 이동할 수 있음

 

해결 방법

1. 쿼터니언 사용

//FQuat은 4차원 회전 표현 방식으로 오일러 각과 달리 회전 축이 사라지는 문제가 없음
FQuat Rotation = FQuat(FVector(0, 1, 0), FMath::DegreesToRadians(90.0f));
Actor->SetActorRotation(Rotation);

 

2. 오일러 각 대신 회전 행렬 사용

FMatrix RotationMatrix = FRotationMatrix::Make(FRotator(90, 0, 0));
FVector NewDirection = RotationMatrix.TransformVector(FVector::ForwardVector);

 

💭회고
드론 제작 해설을 들었는데 내가 무슨 코드를 본 건가 싶었다.
변수도 너무 많았고 물리현상에 대한 많은 고려가 들어가 있어서
배울 점이 많은 코드인 듯 보였다.
이번주와 다음주는 코드에 대한 정리를 하고 가야할 듯 싶다.
(배운 내용이 너무 많아...)