문제

세계 최고의 알고리즘 전문가인 현수의 강연을 보기위해 많은 사람들이 찾아왔습니다.
강연장에는 가로로 c개, 세로로 r개의 좌석이 c×r 격자형태로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다.
아래 그림은 가로 6개, 세로 5개 좌석으로 구성된 6×5격자형 좌석배치입니다.
각 격자에 표시된 (x,y)는 해당 좌석의 번호를 말합니다.
가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (6, 5)이다.

사람들은 온 순서대로 (1,1)위치 좌석부터 시작하여 시계방향으로 돌아 들어가면서 빈 좌석에 앉습니다.
만약 5번째로 온 사람은 (1, 5)좌석에 앉고, 8번째로 온 사람은 (4, 5)좌석에 앉으며, 12번째 온 사람은 (6, 3)좌석에, 20번째 온 사람은 (2, 3) 좌석에 앉게 됩니다.

매개변수 c와 r에 강연장의 크기가 주어지면, k번째로 온 사람이 앉을 좌석번호를 반환하는 프로그램을 작성하세요.
만일 모든 좌석이 배정되어 k번째 온 사람이 앉을 좌석이 없을 경우 [0, 0]을 반환합니다.

입출력 예:

c	r	k	answer
6	5	12	[6, 3]
6	5	20	[2, 3]
6	5	30	[4, 3]
6	5	31	[0, 0]

제한사항:
• 5 ≤ c, r ≤ 1,000이다.
• 1 ≤ k ≤ 100,000,000이다.

접근 방법

문제에 나와있는 대로 한명씩 앉히면 될 것 같은 문제이다.
k의 범위가 크지만 c,r 의 최댓값은 1,000이기 때문에 최대 백만번만 탐색하면 되어 문제없을 듯 하다.
특정한 조건이 없기 때문에 c * r >= k 라면 모든 인원이 앉을 수 있고, 한번 회전하기만 하면 무조건 이동 가능한 문제로 판단했다.

풀이

class Solution {
    public static final int[] dx = {1, 0, -1, 0};
    public static final int[] dy = {0, 1, 0, -1};

    public int[] solution(int c, int r, int k){
        int[] answer = new int[2];

        if (c * r < k) {
            return new int[]{0, 0};
        }
        int[][] board = new int[r][c];

        int x = 0, y = 0, nx = 0, ny = 0, count = 1, idx = 0;
        while (count < k) {
            // 빈자리면 앉히기
            if (board[x][y] == 0) {
                board[x][y] = 1;
                count++;
            }

            nx = x + dx[idx];
            ny = y + dy[idx];
            // 앉을 수 없는 지점이면 회전시키기
            if (nx < 0 || ny < 0 || nx == r || ny == c || board[nx][ny] == 1) {
                idx++;
                idx %= 4;
                nx = x + dx[idx];
                ny = y + dy[idx];
            }
            x = nx;
            y = ny;
        }
        answer[0] = y+1;
        answer[1] = x+1;

        return answer;
    }

    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(Arrays.toString(T.solution(6, 5, 12)));
        System.out.println(Arrays.toString(T.solution(6, 5, 20)));
        System.out.println(Arrays.toString(T.solution(6, 5, 30)));
        System.out.println(Arrays.toString(T.solution(6, 5, 31)));
    }
}