[Stack][Medium] 735. Asteroid Collision

https://leetcode.com/problems/asteroid-collision/description

Asteroid Collision - LeetCode

 

Q. input array ast에서 각 값은 운석의 크기를, 부호는 방향을 의미한다. 
   이때 부호에 대한 방향은 + right, - left 이다.
   충돌시 만나면 크기가 작은것이 폭발하여 없어진다.(같으면 둘다 사라짐)
   방향이 같으면 만나지 않는다.
   모두 속도가 같다고 할때, 충돌 이후 결과를 출력하라.

    ex) [5,10,-5] 
    => 두번째와 세번째가 만나게 되고, 두번째가 크기가 더 크므로 
    => [5,10]

Solution. 

 우선 leet code는 영어사이트 므로, 영어 해석을 잘 해야 풀이가 가능 할 것이다. 처음에 방향에 대한 오역때문에 조금 헷갈렸다. 

 그것만 유의하면, 운석이 왼쪽방향으로 접근할때 이전 운석중에 오른쪽 방향으로 접근하고 있던 것과만 반응하게 된다는 것을 알 수 있다. 따라서 이전 운석이 양방향(오른쪽)일때 stack에 넣고 왼쪽 방향의 값이 오면 연산해 주면 되는 것이다. 

 다만, 현재 왼쪽 방향의 운석이 input 될때, 기존에 우측 방향의 운석이 없다면 아무 일도 일어나지 않는 것에 유의. 

 

코드가 로직 처리상 조금 지저분해 지겠지만, 논리 자체는 명확하다. 

 

vector<int> asteroidCollision(vector<int>& ast)
{
    vector<int> ret;
    stack<int> sBuff;
    for (int k = 0; k < ast.size(); ++k)
    {
        if (ast[k] < 0)				// 좌방향 이동만 연산 처리.
        {
            if (sBuff.empty())		// stack이 비었으면, 만날 다른 운석이 없다.
                sBuff.push(ast[k]);
            else
            {
                while (true)		// 운석이 터지거나, stack이 빌때까지 처리.
                {
                    int last = sBuff.top();
                    if (last < 0)	// 이전것도 좌방향이면 안만난다. - break.
                    {
                        sBuff.push(ast[k]);
                        break;
                    }
                    
                    if (abs(last) < abs(ast[k]))
                        sBuff.pop();// 좌방향이 크면, 기존 stack것 제거. 
                    else if (abs(last) == abs(ast[k]))
                    {
                        sBuff.pop();// 같으면 둘다 제거하고 break.
                        break;
                    }
                    else break;		// 우방향이 크면, 현재상태에서 그냥 break.

                    if (sBuff.empty())
                    {				// 더이상 할 것이 없다. - 넣고 break.
                        sBuff.push(ast[k]);
                        break;
                    }
                }
            }
        }
        else sBuff.push(ast[k]);
    }
    ret.resize(sBuff.size());
    for(int k = 0; k < ret.size(); ++k)
    {
        ret[ret.size() - 1 - k] = sBuff.top();
        sBuff.pop();
    }
    return ret;
}