[LeetCode] 1503. Last Moment Before All Ants Fall Out of a Plank

https://leetcode.com/problems/last-moment-before-all-ants-fall-out-of-a-plank/description/

Last Moment Before All Ants Fall Out of a Plank - LeetCode

leetcode - Last Moment Before All Ants Fall Out of a Plank

문제 유형 : 배열 / 구현

문제 난이도 : Medium

 

 

문제

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with a speed of 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions does not take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank immediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right, return the moment when the last ant(s) fall out of the plank.

 

n의 길이의 나무 판자가 있다. 개미들은 이 나무판자 위를 움직이는데, 초당 1씩 움직일 수 있다. 개미들은 왼쪽으로 움직이거나 오른쪽으로 움직인다.

서로 다른 방향을 가는 두 개미가 마주치면, 그들은 방향을 바꿔 계속 움직인다. 방향을 바꾸는데 시간은 걸리지 않는다.

개미가 끝에 도착하면, 개미는 즉시 떨어진다.

정수 n과 왼쪽으로 가는 개미들의 위치 left, 오른쪽으로 가는 개미들의 위치 right가 주어진다.

개미들이 전부 판자에서 떨어지는 시간을 구하시오.

 

 

풀이

개미가 부딪혀서 방향이 바뀌는 것 때문에 굉장히 복잡한 문제일 것 같지만, 사실은 그렇지 않다.

3에 도착한 왼쪽으로 가는 개미와 3에 도착한 오른쪽 개미가 있다고 해보자. 둘은 마주쳐 방향을 바꾼다.

방향을 바꾸고고, 3의 위치에 있는 개미와 3의 위치에 있는 오른쪽 개미가 있을 뿐이다.

사실상 통과해서 지나가는 것이나 다름없다.

그래서 (왼쪽으로 이동하는 개미의 가장 오른쪽 끝) 과 n - (오른쪽으로 이동하는 개미의 가장 왼쪽 끝) 중에서 더 큰 값을 반환하면 그게 곧 전부 판자에서 떨어지는 시간이다.

 

코드

C++

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        if(left.size() == 0) return n - *min_element(right.begin(), right.end());
        if(right.size() == 0) return *max_element(left.begin(), left.end());
        int minleft = *max_element(left.begin(), left.end());
        int maxRight = n - *min_element(right.begin(), right.end());

        return max(minleft, maxRight);
    }
};