Seating Arrangement 문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

• 현재 좌석이 비어있고 양쪽에 빈 자리가 있는 경우에만 새로운 사람이 앉을수 있다.
• 현재 좌석을 차지하면 양쪽에 새로운 사람이 앉을수 없다.
• possible case
• 000 100 001 [01 [10 [00 10] 01] 00]

시간복잡도: O(m), 공간복잡도: O(1)

class Solution {
    public static boolean is_possible_to_get_seats(int n, int m, int[] seats) {
        int possibleSeat = 0; // 가능한 좌석 수를 저장할 변수

        for (int i = 0; i < m; i++) {
            boolean left = false, right = false; // 왼쪽과 오른쪽에 빈 자리가 있는지 확인하는 변수들

            // 왼쪽에 빈 자리가 있는지 확인
            if (i == 0 || seats[i - 1] == 0) left = true;
            // 오른쪽에 빈 자리가 있는지 확인
            if (i == m - 1 || seats[i + 1] == 0) right = true;

            // 현재 좌석이 비어있고 양쪽에 빈 자리가 있는 경우
            if (seats[i] == 0 && left && right) {
                possibleSeat++; // 가능한 좌석 수를 1 증가시킴
                seats[i] = 1; // 현재 좌석을 차지함
            }
        }
        // 가능한 좌석 수가 필요한 좌석 수보다 많거나 같은 경우 참을 반환, 그렇지 않으면 거짓을 반환
        return possibleSeat >= n;
    }
}

설명

• 처음에는 if (seats[i] == 0 && (i == 0 || seats[i - 1] == 0) && (i == m - 1 || seats[i + 1] == 0)) 이런식으로 짯었는데, 천천히 하나씩 분리해서 짜면 훨씬 가독성도 좋고 만들기도 쉽다.