기둥과 보 설치
문제 해석
기둥과 보를 설치 또는 삭제한 결과를 리턴하는 문제입니다.
기둥은 다음의 조건을 만족할 시, 설치가 가능합니다.
- 설치할 기둥이 바닥 위인 경우
- 설치할 기둥이 보의 한쪽 끝부분 위에 있는 경우
- 설치할 기둥이 다른 기둥 위에 있는 경우
보는 다음의 조건을 만족할 시, 설치가 가능합니다.
- 한쪽 끝부분이 기둥 위에 있는 경우
- 양쪽 끝부분이 다른 보와 동시에 연결되어있는 경우
구조물을 삭제할 때, 이미 설치된 구조물이 설치 조건에 맞지 않으면 삭제할 수 없습니다.
설계(20)
별도의 알고리즘이 필요없는 구현문제입니다.
여기서 키포인트는 입력좌표를 변환시켜주는 것, 설치와 삭제 조건 맞추기 입니다.
주의할 점은 한 좌표에 기둥과 보가 같이 설치될 수 있다는 점입니다.
각 좌표에 기둥과 보가 설치될 것을 고려하여 3차원배열 arr[x][y][기둥,보]을 사용합니다.
삭제할 때 삭제할 구조물 주변을 살펴봐야하지만, 조건이 다양해서 그냥 모든 배열을 조사해서 다른 구조물이 설치 조건에 부합하는지 체크하는 방식으로 구성하였습니다.
구현(50)
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int arr[101][101][2];
bool check(int x, int y, int a, int n) {
if (a == 0) {
if (x == n || arr[x][y][1] || arr[x][y - 1][1] || (x + 1 <= n && arr[x + 1][y][0])) return true;
}
else {
if (arr[x + 1][y][0] || arr[x + 1][y + 1][0] || (arr[x][y - 1][1] && arr[x][y + 1][1])) return true;
}
return false;
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int> > answer;
// [x,y,a,b] : x,y는 좌표, a는 구조물(0:기둥,1:보)
// b는 설치 또는 삭제 (0: 삭제, 1: 설치)
for (int i = 0; i < build_frame.size(); i++) {
int x = n - build_frame[i][1];
int y = build_frame[i][0];
int a = build_frame[i][2];
int b = build_frame[i][3];
// 설치하는경우
if (b == 1) {
if (check(x, y, a,n)) {
arr[x][y][a] = 1;
}
}
else {
arr[x][y][a] = 0;
bool possible = true;
for (int j = 0; j <= n&&possible; j++) {
for (int k = 0; k <= n; k++) {
if (arr[j][k][0]) {
if (!check(j, k, 0,n)) {
possible = false;
break;
}
}
if (arr[j][k][1]) {
if (!check(j, k, 1,n)) {
possible = false;
break;
}
}
}
}
if (!possible) arr[x][y][a] = 1;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (arr[i][j][0]) {
answer.push_back({ j,n - i,0 });
}
if (arr[i][j][1]) {
answer.push_back({ j,n - i,1 });
}
}
}
sort(answer.begin(), answer.end());
return answer;
}
디버깅
어이없는 실수로 디버깅에 엄청난 시간을 쏟아부었습니다.
한 좌표에 기둥 또는 보가 모두 설치되어있을 수 있습니다. 그래서 기둥인 경우 보인 경우 독립적으로 조건을 찾아봐야했으나, if와 else if문으로 작성하여 한 조건만 찾게 코드를 구성하는 실수를 하였습니다.
if와 if로 독립적으로 변경시켜주니 알맞게 코드가 작동하였습니다.
제출결과
마무리
삼성전자 코딩테스트 스타일의 구현문제였습니다.
좌표를 꼬아서 낸 것과 구조물이 겹치는 것을 조심하면 빠른시간 안에 구현이 가능했을 듯 합니다.