[LeetCode] 2582. Pass the Pillow

https://leetcode.com/problems/pass-the-pillow/description/

leetcode - Pass the Pillow

문제 유형 : 수학, 구현

문제 난이도 : Easy

 

문제

There are n people standing in a line labeled from 1 to n. The first person in the line is holding a pillow initially. Every second, the person holding the pillow passes it to the next person standing in the line. Once the pillow reaches the end of the line, the direction changes, and people continue passing the pillow in the opposite direction.

• For example, once the pillow reaches the nth person they pass it to the n - 1th person, then to the n - 2th person and so on.

Given the two positive integers n and time, return the index of the person holding the pillow after time seconds.

 

n명의 사람이 1부터 n까지의 번호로 부여되어 나란히 있다.

첫 번째 사람이 처음에 배게를 갖는다.

매 초마다, 다음사람에게 배게를 전달한다.

끝에 도달하면, 방향을 바꾼다.

 

두 개의 정수 n과 time이 주어진다. time초가 지나고 몇 번째 사람이 배게를 갖고 있는지 알아내시오.

 

풀이

수학적으로 풀 수 있다.

n = 4인경우, 1 2 3 4 3 2 의 패턴을 그린다.

즉, 2(n-1)마다 반복된다.

 

그러므로, x = time % N으로 사이클 내의 인덱스를 구한다.

만약 x가 n보다 크면, N-x를, 아니면 그냥 x를 1에 더하여(모듈러에 의해 0-indexed기준으로 구해진것이라 1 추가가 필요하다.)

반환한다.

 

코드

C++

class Solution {
public:
    int passThePillow(int n, int time) {
        int N = 2 * (n-1), x = time % N;
        return 1+(x < n? x : N-x);
    }
};