[프로그래머스][C++] 거리두기 확인하기
거리두기 확인하기
문제 링크
분석
대기실은 5개이며, 각 대기실이 5x5 크기라는 것은 배열이 5x5로 주어진다는 의미입니다.
즉, 2차원 배열이고 각 크기는 5입니다.
맨해튼 거리는 두 점(x1, y1), (x2, y2) 간의 거리를 의미합니다.
abs(x1 - x2) + abs(y1 - y2)으로 계산할 수 있습니다.
만약 (0,0), (0,1)인 경우 거리는 1입니다.
만약 (0,0), (1,1)인 경우 거리는 2입니다.
만약 (0,0), (2,0)인 경우 거리는 2입니다.
맨해튼 거리가 거리가 2 이하인 경우, 파티션으로 막혀있지 않다면 거리두기에 실패합니다.
각 대기실이 거리두기를 지켰으면 1, 아니면 0으로 나타낸 배열을 반환해야합니다.
vector<vector<string>> places는 3차원 배열이라고 볼 수 있습니다.
places[i][j][k]라고 할 때, i는 대기실 번호, j는 세로 방향(행), k는 가로 방향(열)을 의미합니다.
문자열의 각 문자는 다음과같은 의미를 가집니다.
P 사람, O 빈 테이블, X 파티션
풀이
#include <string>
#include <vector>
using namespace std;
// 특정 위치에서 확인할 방향 벡터
// 직선으로 거리 1인 경우
int dx1[4] = {1, -1, 0, 0};
int dy1[4] = {0, 0, 1, -1};
// 직선으로 거리 2인 경우
int dx2[4] = {2, -2, 0, 0};
int dy2[4] = {0, 0, 2, -2};
// 대각선인 경우
int dxDiag[4] = {1, 1, -1, -1};
int dyDiag[4] = {1, -1, 1, -1};
// 각 대기실이 거리두기를 지키는지 검사하는 함수
bool checkRoom(const vector<string>& room)
{
// 모든 칸 순회
for (int y = 0; y < room.size(); ++y)
{
for (int x = 0; x < room[0].size(); ++x)
{
// 현재 위치가 사람이 아니라면 넘어간다.
if (room[y][x] != 'P')
{
continue;
}
// 상하좌우로 거리1에 다른 사람이 있는지 확인
for (int d = 0; d < 4; ++d)
{
int nx = x + dx1[d];
int ny = y + dy1[d];
// 범위 밖 스킵
if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
// 바로 옆에 사람이 있다면 거리두기 위반
if (room[ny][nx] == 'P') return false;
}
// 상하좌우로 거리2에 다른 사람이 있는지 확인
for (int d = 0; d < 4; ++d)
{
int nx = x + dx2[d];
int ny = y + dy2[d];
// 범위 밖 스킵
if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
// 거리가 2인 곳에 다른 사람이 있는 경우
if (room[ny][nx] == 'P')
{
int mx = x + dx1[d];
int my = y + dy1[d];
// 가운데에 파티션이 없다면 거리두기 위반
if (room[my][mx] != 'X') return false;
}
}
// 대각선 검사
for (int d = 0; d < 4; ++d)
{
int nx = x + dxDiag[d];
int ny = y + dyDiag[d];
// 범위 밖 스킵
if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
// 대각선에 사람이 있는 경우
if (room[ny][nx] == 'P')
{
int mx1 = x;
int my1 = ny;
int mx2 = nx;
int my2 = y;
// 다른 사람과 인접한 칸 중 파티션이 하나라도 없으면 거리두기 위반
if (room[my1][mx1] != 'X' || room[my2][mx2] != 'X') return false;
}
}
}
}
// 모든 칸을 검사한 결과 문제가 없는 경우
return true;
}
vector<int> solution(vector<vector<string>> places) {
vector<int> answer;
// 각 대기실 검사
for (const vector<string>& room : places)
{
if (checkRoom(room))
{
answer.push_back(1);
}
else
{
answer.push_back(0);
}
}
return answer;
}
성능 요약
시간 복잡도는 $O(n \times m^2)$입니다.
- 대기실의 개수 5, 대기실의 크기 5x5, 각 거리와 각 방향 검사 12 $O(5 \times 5 \times 5 \times 12)$
- 일반화할 경우 $O(n \times m^2)$
공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.
테스트 1 〉 통과 (0.02ms, 4.15MB)
테스트 2 〉 통과 (0.01ms, 4.08MB)
테스트 3 〉 통과 (0.02ms, 4.15MB)
테스트 4 〉 통과 (0.01ms, 4.01MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.25MB)
테스트 8 〉 통과 (0.01ms, 4.15MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.16MB)
테스트 11 〉 통과 (0.01ms, 4.15MB)
테스트 12 〉 통과 (0.01ms, 4.14MB)
테스트 13 〉 통과 (0.01ms, 4.45MB)
테스트 14 〉 통과 (0.01ms, 3.68MB)
테스트 15 〉 통과 (0.01ms, 4.22MB)
테스트 16 〉 통과 (0.02ms, 4.18MB)
테스트 17 〉 통과 (0.01ms, 4.03MB)
테스트 18 〉 통과 (0.02ms, 4.22MB)
테스트 19 〉 통과 (0.02ms, 4.21MB)
테스트 20 〉 통과 (0.02ms, 4.22MB)
테스트 21 〉 통과 (0.01ms, 4.22MB)
테스트 22 〉 통과 (0.01ms, 4.14MB)
테스트 23 〉 통과 (0.01ms, 4.22MB)
테스트 24 〉 통과 (0.01ms, 4.01MB)
테스트 25 〉 통과 (0.01ms, 4.14MB)
테스트 26 〉 통과 (0.01ms, 4.22MB)
테스트 27 〉 통과 (0.01ms, 4.15MB)
테스트 28 〉 통과 (0.01ms, 4.21MB)
테스트 29 〉 통과 (0.01ms, 4.21MB)
테스트 30 〉 통과 (0.01ms, 4.14MB)
테스트 31 〉 통과 (0.02ms, 4.21MB)
댓글남기기