[LeetCode] 2751. Robot Collisions

https://leetcode.com/problems/robot-collisions/description/

leetcode - Robot Collisions

문제 유형 : 스택

문제 난이도 : Hard

 

문제

There are n 1-indexed robots, each having a position on a line, health, and movement direction.

You are given 0-indexed integer arrays positions, healths, and a string directions (directions[i] is either 'L' for left or 'R' for right). All integers in positions are unique.

All robots start moving on the line simultaneously at the same speed in their given directions. If two robots ever share the same position while moving, they will collide.

If two robots collide, the robot with lower health is removed from the line, and the health of the other robot decreases by one. The surviving robot continues in the same direction it was going. If both robots have the same health, they are both removed from the line.

Your task is to determine the health of the robots that survive the collisions, in the same order that the robots were given, i.e. final heath of robot 1 (if survived), final health of robot 2 (if survived), and so on. If there are no survivors, return an empty array.

Return an array containing the health of the remaining robots (in the order they were given in the input), after no further collisions can occur.

Note: The positions may be unsorted.

 

로봇들이 줄 위에 서있다. 각자 체력과 이동 방향이 정해져있다.

배열 positions, healths, 그리고 문자열 directions가 주어진다.

각각의 i번째 요소는 i번째 로봇의 정보이다.

모든 로봇은 동시에 같은 속도로 정해진 방향대로 움직인다.

만약 두 로봇의 위치가 겹치면, 충돌한다.

 

만약 두 로봇이 충돌하면, 

더 적은 체력의 로봇이 사라지고, 더 많은 쪽은 체력이 1 감소한다.

둘의 체력이 같다면, 둘다 사라진다.

당신은 더 이상 아무리 이동해도 충돌이 없을 때의 각 로봇의 체력을 반환해야 합니다.

로봇의 정보가 주어진 순서로 반환하시오.

로봇들의 위치는 정렬되어있지 않습니다.

 

풀이

우선, 로봇에 대한 구조체(또는 클래스)를 만들어서 각각의 id, 위치, 체력, 이동방향을 저장시켜야 한다.

Robot 자료형에 대한 배열 Robots를 만들어서 순차적으로 i+1번쨰 로봇을 읽으며, Robots배열을 채운다.

 

그 뒤, Robots배열을 위치기준 오름차순으로 정렬해준다.

Robots형을 담을 스택을 하나 만든다. 이 스택에는 R방향으로 향하는 살아남은 로봇들이 있을 것이다.

순차적으로 Robots배열을 순회하면서...

  이동방향이 R인 경우, 스택에 넣는다.

  이동방향이 L인 경우, R인 로봇들과 충돌한다. 근데, 가장 오른쪽에 있는 로봇부터 충돌하므로 스택의 톱부터 충돌시킨다.

    충돌은 문제의 규칙대로 구현해주면 된다.

    (예를 들면, L로봇보이 크면 스택 pop후, L로봇의 체력 낮추기, 같으면 스택 pop후, L로봇의 체력을 0으로 설정. L로봇이 더 작으면 체력을 0으로 설정. 이를 L로봇의 체력이 0보다 크거나 스택이 empty가 아닌동안 하면 된다.)

    L로봇에 대한 충돌이 끝나고, L로봇이 살아있다면, survivied배열에 담는다.

 

순회가 끝나고, 스택의 요소들을 빼서 survived에 넣는다. 그리고 survived를 id에 따라서 정렬하고, survived의 각 로봇의 체력만 정수형 배열에 순차적으로 담아서 반환하면 된다.

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

struct Robot {
    int id;
    int position;
    int health;
    char direction;
};

class Solution {
public:
    vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) {
        vector<Robot> Robots;
        for(int i = 0; i < positions.size(); i++) {
            Robots.push_back({i+1, positions[i], healths[i], directions[i]});
        }

        sort(Robots.begin(), Robots.end(), [](const auto &a, const auto &b){
            return a.position < b.position;
        });

        vector<Robot> survived;
        stack<Robot> st;
        for(int i = 0; i < Robots.size(); i++) {
            if(Robots[i].direction == 'R') {
                st.push(Robots[i]);
            } else {
                while(st.size() > 0 && Robots[i].health > 0) {
                    if(st.top().health < Robots[i].health) {
                        st.pop();
                        Robots[i].health--;
                    } else if(st.top().health == Robots[i].health) {
                        st.pop();
                        Robots[i].health = 0;
                    } else {
                        st.top().health--;
                        Robots[i].health = 0;
                    }
                }
                if(Robots[i].health > 0) survived.push_back(Robots[i]);
            }
        }

        while(!st.empty()) {
            survived.push_back(st.top());
            st.pop();
        }

        sort(survived.begin(), survived.end(), [](const auto &a, const auto &b){
            return a.id < b.id;
        });

        vector<int> ans;
        for(const auto r : survived) {
            ans.push_back(r.health);
        }

        return ans;
    }
};