▼ 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이다.
입출력 예
어떻게 해결해야 할까 ?
- 문제에서 제시해준 격자를 시계방향으로 90도 돌려서 생각해보자
- 다음 사람을 앉힐 좌석의 위치를 저장할 일차원 배열 'answer'와 좌석에 사람이 앉아있는지 체크할 boolean형 배열 'seats'을 하나 생성해준다
- 일단, 다음 사람을 앉힐 좌석의 위치를 다음('tmpX', 'tmpY')으로 변경하기 전에 생각해야 할 것이 두 가지 있다
- boolean형 배열에 현재 좌석('answer')에 사람을 앉혔다는 표시를 먼저 해줘야 한다
- 다음 위치로 옮겨도 격자 밖으로 벗어나거나 사람이 이미 앉아있지 않은지를 먼저 체크하고, 문제가 있다면 이동 방향을 시계 방향으로 90도 회전시키고 해당 방향으로 좌석의 위치를 이동시켜야 한다
- k번째로 온 사람이 좌석이 앉거나 좌석이 다 찰 때까지 반복해야 하기 때문에, for문보다는 while문이 적합할 것 같다
- 현재 앉아있는 관객의 수를 저장할 변수 'audience'를 하나 생성해준다
- 'answer'는 이번 사람이 아닌 다음 사람을 앉힐 좌석의 위치이기 때문에, k-1명을 자리에 앉힐때까지 while문이 반복되도록 해야 한다
➜ 그래야 'answer'에 k번째 사람(다음 사람)이 앉을 위치가 저장된 상태로 반환될 수 있다
( k번째 사람을 앉혔을 때 answer를 반환한다면, k+1번째 사람이 앉을 좌석의 위치가 반환되는 것이다 ) - 좌석의 개수가 k보다 크다면 바로 while문을 빠져나가 [0, 0]을 반환하도록 해두자
- 단, 좌석의 시작 위치 값은 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;
}
}
▼ 정리
- 이번 문제를 해결할 때 특정 입력에 따라 원치 않은 결과를 출력하는 원인을 찾는 데 시간이 꽤 오래 걸렸는데, 그 원인은 반복문의 조건을 잘못 설정해둔 것이었다
➜ 반복문은 생각치 못한 부분으로 인해 발생한 아주 작은 차이(종료지점)로도 원치 않은 결과가 출력될 수 있다는 것을 느꼈다 - 내가 해당 문제를 해결하려는 방향을 좀더 체계적으로 생각해두고, 반복문이 수행되는 조건을 그 방향에 맞게 미리 잘 설정해서 쓸데없는 곳에 시간을 뺏기지 않도록 주의하자 !
