LeetCode 2582. Pass the Pillow 자바 문제 풀이

문제 설명

• 문제: https://leetcode.com/problems/pass-the-pillow/description/
• 설명: 1번부터 n번까지의 사람이 원형으로 서 있습니다. 1번 사람이 베개를 가지고 있고, 매 시간마다 베개를 오른쪽으로 한 사람에게 전달합니다.마지막에 도달하면 반대로 n번에서 1번으로 베개를 전달합니다. time 시간 후에 베개를 가진 사람의 번호를 반환하세요.

접근 방식

• 아이디어:
  • 문제를 더 쉽게 이해하기 위해 전체 원을 몇 바퀴 도는지를 먼저 계산합니다.
  • 각 바퀴는 n-1 시간이 걸리므로 time / (n-1)을 통해 전체 바퀴 수를 구합니다.
    • n이 4일 경우, 1에서 3번 이동해야 4에 도착합니다. 1→2→3→4
  • 그 후 남은 시간을 time % (n-1)으로 구하고, 이 값을 이용하여 베개가 마지막 바퀴에서 몇 번째 사람에게 전달되는지를 계산합니다.
  • 전체 바퀴 수가 짝수인지 홀수인지에 따라 방향이 달라지므로, 짝수 바퀴와 홀수 바퀴에 대해 각각 다른 사람에게 베개가 전달됩니다.
• 알고리즘:
  1. arrow 변수에 전체 바퀴 수를 저장합니다. arrow = time / (n-1)
  2. counter 변수에 마지막 바퀴에서 몇 번째 사람까지 베개가 전달되었는지를 저장합니다. counter = time % (n-1)
  3. arrow가 짝수인 경우와 홀수인 경우에 따라 결과를 계산합니다.
     • arrow가 짝수인 경우, 앞에서부터 베개를 전달하므로: 1 + counter
     • arrow가 홀수인 경우, 뒤에서부터 베개를 전달하므로: n - counter

코드

class Solution {
    public int passThePillow(int n, int time) {
        int arrow = time / (n-1);
        int counter = time % (n-1);
        int result;

        if (arrow % 2 != 0) {
            result = n - counter;
        } else {
            result = 1 + counter;
        }

        return result;
    }
}

결론

• 시간 복잡도:
  • 모든 연산이 상수 시간 내에 이루어지므로 시간 복잡도는 O(1)입니다.
• 공간 복잡도:
  • 추가적인 공간을 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다.