Algorithm

[PCCP] 마무리 [2]

Uykm 2023. 8. 20. 00:29

▼ What ?

이번에도 구현 - 시뮬레이션 유형의 문제를 풀어보려고 한다.

▼ 좌석 번호

 

문제 정보

세계 최고의 알고리즘 전문가인 현수의 강연을 보기위해 많은 사람들이 찾아왔습니다.

강연장에는 가로로 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]을 반환합니다.

 

제한 사항

  • 5 ≤ c, r ≤ 1,000이다.
  • 1 ≤ k ≤ 100,000,000이다.

 

입출력 예

 

어떻게 해결해야 할까 ?

  1. 문제에서 제시해준 격자를 시계방향으로 90도 돌려서 생각해보자
  2. 다음 사람을 앉힐 좌석의 위치를 저장할 일차원 배열 'answer'와 좌석에 사람이 앉아있는지 체크할 boolean형 배열 'seats'을 하나 생성해준다
  3. 일단, 다음 사람을 앉힐 좌석의 위치를 다음('tmpX', 'tmpY')으로 변경하기 전에 생각해야 할 것이 두 가지 있다
    • boolean형 배열에 현재 좌석('answer')에 사람을 앉혔다는 표시를 먼저 해줘야 한다
    • 다음 위치로 옮겨도 격자 밖으로 벗어나거나 사람이 이미 앉아있지 않은지를 먼저 체크하고, 문제가 있다면 이동 방향을 시계 방향으로 90도 회전시키고 해당 방향으로 좌석의 위치를 이동시켜야 한다
  4. k번째로 온 사람이 좌석이 앉거나 좌석이 다 찰 때까지 반복해야 하기 때문에, for문보다는 while문이 적합할 것 같다
  5. 현재 앉아있는 관객의 수를 저장할 변수 'audience'를 하나 생성해준다
  6. 'answer'는 이번 사람이 아닌 다음 사람을 앉힐 좌석의 위치이기 때문에, k-1명을 자리에 앉힐때까지  while문이 반복되도록 해야 한다
    ➜ 그래야 'answer'에 k번째 사람(다음 사람)이 앉을 위치가 저장된 상태로 반환될 수 있다
    ( k번째 사람을 앉혔을 때 answer를 반환한다면, k+1번째 사람이 앉을 좌석의 위치가 반환되는 것이다 )
  7. 좌석의 개수가 k보다 크다면 바로 while문을 빠져나가 [0, 0]을 반환하도록 해두자
  8. 단, 좌석의 시작 위치 값은 0이 아닌 1부터 시작하기 때문에 'answer'를 반환하기 전에 'answer[0]'과 'answer[1]'에 1을 더해줘야 문제에서 원하는 결과값을 반환할 수 있다

 

해결 코드

public class Solution {
    public int[] solution(int c, int r, int k){
        int[] answer = new int[2];
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        int dir = 1;
        boolean[][] seats = new boolean[c][r];

        // 현재 앉아있는 관객의 수
        int audience = 0;

        while(audience < k - 1) { // audience의 값이 (k-1)이라면 반복문을 수행하지 않도록 한다

            // k가 좌석의 수를 넘어갈 경우
            if(k > c * r) return answer;

            int tmpX = answer[0] + dx[dir]; int tmpY = answer[1] + dy[dir];

            if(tmpX < 0 || tmpX >= c || tmpY < 0 || tmpY >= r || seats[tmpX][tmpY] == true) {
                dir = (dir + 1) % 4;
                continue;
            }
            
            // 좌석에 사람을 앉혔다
            seats[answer[0]][answer[1]] = true;
            audience++;
			
            // 다음 사람을 앉힐 좌석의 위치 저장
            answer[0] = tmpX; answer[1] = tmpY;
        }

        answer[0] += 1; answer[1] += 1;

        return answer;
    }
}

 

▼ 정리

 

  • 이번 문제를 해결할 때 특정 입력에 따라 원치 않은 결과를 출력하는 원인을 찾는 데 시간이 꽤 오래 걸렸는데, 그 원인은 반복문의 조건을 잘못 설정해둔 것이었다

    ➜ 반복문은 생각치 못한 부분으로 인해 발생한 아주 작은 차이(종료지점)로도 원치 않은 결과가 출력될 수 있다는 것을 느꼈다

  • 내가 해당 문제를 해결하려는 방향을 좀더 체계적으로 생각해두고, 반복문이 수행되는 조건을 그 방향에 맞게 미리 잘 설정해서 쓸데없는 곳에 시간을 뺏기지 않도록 주의하자 !