문제 출처
나의 풀이 (실패)
풀지 못한 이유 찾기
설치에 대해 데이터를 저장할 때, 데이터를 가공하지 않고 단순히 주어진 대로 즉, [x,y,a,b] 형태로 저장하려고 했다. 그러다 보니 복잡도가 급격히 증가했다.
그럴 필요 없이 좌표 형태로 배열에 저장하면 되는 거였는데, 그렇게 생각하지 못했다. 여기서 꼬이기 시작했다.
삭제를 했을 때, 건축물이 규칙을 만족해야 한다는 말에 꽂혀서
연속적으로 조건을 충족해야 한다고 생각했다.
마치 미로 문제처럼 계속해서 연속적으로 값을 누적하며 전진해서 설치가 완성된다고 생각했다.
그래서 재귀로 접근하려 했으나 그럴 필요가 없었다.
단순히 설치와 삭제를 구분한 뒤,
주어지는 각각의 입력에 대해 삭제할 수 있는지 설치할 수 있는지만 고려하면 되는 문제였다.
- 이전 정보가 바탕되어야만 현재 값을 결정할 수 있는가? => 재귀 가능
- 현재 값은 결정되어 있지만, 이전 정보를 활용하는 정도의 분리 관계가 가능하면 => 재귀를 쓸 필요가 없다.
이 문제를 보면 설치하는 데 있어 이미 좌표 데이터를 제공해준다. 이 좌표 데이터를 형성하기 위해서 이전 데이터가 필요한 게 아니다. 이미 만들어진 좌표 데이터를 어떻게 저장할 지에 대해 이전 데이터들이 필요한 것 뿐이다.
요약하자면,
재귀적으로 사고해야 할 경우와 아닌 경우를 구분하지 못하고 있었다.
그러다 보니 처음 데이터 생성 부분(어떤 식으로 배열을 생성하고 // 몇 개의 배열이 필요하고 // 배열에 어떤 데이터를 어떻게 저장해야 하는지)부터 꼬였다.
다른 풀이
문제를 푸는 데 있어 필요한 건 2가지이다.
- 기둥과 보를 설치할 수 있는지 판단
- 기둥과 보를 삭제할 수 있는지 판단
1. 배열 크기 설정
설치부터 생각해보면 기둥과 보를 설치해야 하는데,
기둥과 보를 설치할 수 있는 조건은 다음과 같다.
- 기둥은 교차점 좌표를 기준으로 위로 설치된다.
- 보는 교차점 좌표를 기준으로 오른쪽으로 설치된다.
좌표 형태로 데이터를 저장할텐데, 어떤 좌표가 기둥인지 보인지 등의 정보를 담으려면
NxN 보드일 때, 데이터는 (N+1)x(N+1)로 생성을 해야 한다.
예를 들어 (x,y)좌표로 고려하면
(0,0)에서 기둥을 설치하면 (0,0)에서 (0,1)까지의 좌표가 기둥에 포함된다.
2. 배열 개수
기둥과 보가 하나의 교점좌표에 동시에 존재할 수 있다.
즉, 하나의 좌표에 2개의 데이터를 저장해야 한다.
간편하게 데이터를 다루려면 배열을 2개 만드는 게 좋다.
그러므로 (N+1)x(N+1) 크기의 배열을 2개 만들어서,
하나는 기둥 설치 여부
다른 하나는 보 설치 여부를 저장하면 된다.
3. build_frame
build_frame에는 다음과 같이 입력값이 주어진다.
[ x좌표, y좌표, 건축물(보 또는 기둥), 명령(설치 또는 또는) ]
각 주어지는 입력값에 대해서 다음과 같이 조건을 나눠 해결해야 한다.
- 설치 명령 => 기둥을 설치할 수 있는 조건 판별
- 설치 명령 => 보를 설치할 수 있는 조건 판별
- 삭제 명령 => 삭제할 수 있는 조건 판별
- 설치 명령 && 기둥 설치
설치 좌표(x,y)에 대해 기둥을 설치하려면 다음과 같은 조건 중 하나라도 부합하면 된다.
- 설치 좌표의 y가 0이거나
(x, 0) - 설치 좌표 바로 밑에 기둥이 설치되어 있거나
(x,y-1) - 설치 좌표가 보의 왼쪽 좌표이거나
(x, y) - 설치 좌표가 보의 오른쪽 좌표이거나
(x-1, y)
- 설치 명령 && 보 설치
설치 좌표(x,y)를 기준으로 보를 설치하려면 다음 조건 중 하나라도 해당하면 된다.
- 설치 좌표(x,y)를 기준으로 양 끝에 1만큼 떨어져 있는 좌표
{ (x+1,y), (x-1,y) }에 보가 설치되어 있거나 - 바로 아래에 기둥이 설치되어 있거나
(x, y-1) - 바로 아래 오른쪽에 기둥이 설치되어 있거나
(x+1, y-1)(왜냐면 보는 오른쪽으로 눕혀서 설치되므로)
- 삭제 명령
단순하게 설치되어 있는 보를 찾아서 제거해보고
모든 요소의 설치 조건 부합하는지 체크하는 게 가장 간단한다.
효율성을 따진다면, 기둥과 보의 경우를 나눠서 삭제 조건을 따져봐야 한다.
기둥의 경우, 다음 경우의 수를 갖는다.
- 기둥 윗 부분에 기둥이 설치된 경우
- 기둥 바로 위에 보가 설치된 경우 (보의 왼쪽 좌표가 기둥 바로 위인 경우)
- 기둥 바로 위 왼쪽에 보가 설치된 경우 (보의 오른쪽 좌표가 기둥 바로 위인 경우)
보의 경우, 다음 경우의 수를 갖는다.
- 현재 위치에 설치된 기둥
- 현재 위치에서 오른쪽에 설치된 기둥
- 현재 위치에서 왼쪽에 설치된 보
- 현재 위치에서 오른쪽에 한칸 떨어져서 설치된 보
아래 풀이에서의 삭제 처리는 효율성을 고려하지 않고 전체 탐색한 코드이다.
function solution(n, build_frame) {
const answer = [];
const col = Array.from(Array(n+1), () => Array(n+1).fill(0)) // 기둥
const row = Array.from(Array(n+1), () => Array(n+1).fill(0)) // 보
/**
* 해당 설치 좌표(y,x)에 건축물(기둥 혹은 보) 설치 가능 여부 판단
* 배열 좌표에서 y의 index는 반대가 된다
* 즉, 한칸 뒤에 있으면 y+1 이 아니라 y-1이 되고, y==0 이면 y==n 으로 고려해야 한다.
*/
const installable = (y, x, type) => {
if(type == 0){ // 기둥
if(y == n) return true // (y == 0) 이거나
if(col[y + 1][x]) return true // 바로 아래에 기둥이 설치되어 있거나 (y-1, x)
if(row[y][x] || (x>0 && row[y][x - 1])) return true // 설치 좌표 혹은 설치 좌표의 왼쪽에 보가 설치되어 있거나
}
else { // 보
if(col[y + 1][x] || (x<n && col[y + 1][x + 1])) return true // 바로 아래 기둥이 설치되어 있거나 혹은 바로 아래 오른쪽에 기둥이 설치되어 있거나
if(x>0 && row[y][x - 1] && row[y][x + 1]) return true // 왼쪽과 오른쪽에 모두 보가 설치되어 있거나
}
return false
}
/**
* 삭제 조건 - 단순히 지워보는 방식으로
* 삭제 대상 좌표를 지워본 뒤에, "모든" 기둥과 보가 여전히 설치조건을 만족하는지 판단한다.
*/
const removable = () => {
// 기둥
for(let i=1; i<=n; i++){ // 기둥은 설치 좌표의 한 칸 위에 체크했으므로 (i=1)
for(let j=0; j<=n; j++){ // 보의 경우 오른쪽까지 설치 여부가 체크되므로 (<=n)
if(!col[i][j]) continue
if(!installable(i, j, 0)) return false
}
}
// 보
for(let i=0; i<n; i++){
for(let j=0; j<n; j++){
if(!row[i][j]) continue
if(!installable(i, j, 1)) return false
}
}
return true
}
/**
* 명령 수행 : 건축물 설치/삭제
*/
build_frame.forEach(([x, y, type, command]) => {
y = n - y // 배열 index에서 y값이 달라져야 하므로
if(command == 1){ // 설치
if(type == 0 && installable(y, x, 0)) col[y][x] = 1 // 기둥 설치
else if(type == 1 && installable(y, x, 1)) row[y][x] = 1 // 보 설치
}
else { // 삭제
if(type == 0){ // 기둥 삭제
col[y][x]=0
if(!removable()) col[y][x] = 1 // 지워보고 전부 체크해봤는데 불가능하면 다시 되돌려놓기
}
else { // 보 삭제
row[y][x] = 0
if(!removable()) row[y][x] = 1
}
}
})
// 정답으로 변환
for(let j=0; j<=n; j++){
for(let i=n; i>=0; i--){
if(col[i][j]) answer.push([j, n-i, 0])
if(row[i][j]) answer.push([j, n-i, 1])
}
}
return answer
}다른 풀이 2
function solution(n, build_frame) {
let answer = [];
let bo = Array(n + 2)
.fill(null)
.map(() => Array());
let pillar = Array(n + 2)
.fill(null)
.map(() => Array());
for (let [x, y, a, b] of build_frame) {
// 설치
if (b == 1) {
if (a == 0) {
add_pill(x, y, pillar, bo);
} else if (a == 1) {
add_bo(x, y, pillar, bo);
}
}
// 삭제
else if (b == 0) {
delete_frame(x, y, a, pillar, bo, n);
}
}
for (let i = 0; i < n + 1; i++) {
for (let j = 0; j < n + 1; j++) {
if (pillar[i][j]) answer.push([i, j, 0]);
if (bo[i][j]) answer.push([i, j, 1]);
}
}
return answer;
}
function add_pill(x, y, pillar, bo) {
// 바닥 위
if (y == 0) {
pillar[x][y] = 1;
return true;
}
// 다른 기둥 위에
if (y >= 1 && pillar[x][y - 1]) {
pillar[x][y] = 1;
return true;
}
/* 보 */
if (x >= 1 && bo[x - 1][y]) {
pillar[x][y] = 1;
return true;
}
if (bo[x][y]) {
pillar[x][y] = 1;
return true;
}
return false;
}
function add_bo(x, y, pillar, bo) {
// 보는 한쪽 끝 부분이 기둥 위에 있거나,
if (y >= 1 && pillar[x][y - 1]) {
bo[x][y] = 1;
return true;
}
if (y >= 1 && pillar[x + 1][y - 1]) {
bo[x][y] = 1;
return true;
}
// 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
if (x >= 1 && bo[x - 1][y] && bo[x + 1][y]) {
bo[x][y] = 1;
return true;
}
return false;
}
// 0:기둥, 1:보
function delete_frame(x, y, frame, pillar, bo, n) {
let flag = true;
if (frame == 0) pillar[x][y] = 0;
else bo[x][y] = 0;
for (let i = 0; i < n + 1; i++) {
for (let j = 0; j < n + 1; j++) {
let testPillar = pillar[i][j];
if (testPillar == 1) {
testPillar = 0;
if (!add_pill(i, j, pillar, bo)) flag = false;
testPillar = 1;
}
let testBo = bo[i][j];
if (testBo == 1) {
testBo = 0;
if (!add_bo(i, j, pillar, bo)) flag = false;
testBo = 1;
}
}
if (!flag) break;
}
if (!flag) {
if (frame == 0) pillar[x][y] = 1;
else bo[x][y] = 1;
}
return flag;
}참고
