-
프로그래머스 코딩테스트 연습 - 기둥과 보 설치 (구현) 본문
# 주소
https://school.programmers.co.kr/learn/courses/30/lessons/60061
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
# 문제
문제 설명
빙하가 깨지면서 스노우타운에 떠내려 온 "죠르디"는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. "죠르디"는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있습니다.
프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다.
- 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
- 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
단, 바닥은 벽면의 맨 아래 지면을 말합니다.
2차원 벽면은 n x n 크기 정사각 격자 형태이며, 각 격자는 1 x 1 크기입니다. 맨 처음 벽면은 비어있는 상태입니다. 기둥과 보는 격자선의 교차점에 걸치지 않고, 격자 칸의 각 변에 정확히 일치하도록 설치할 수 있습니다. 다음은 기둥과 보를 설치해 구조물을 만든 예시입니다.
예를 들어, 위 그림은 다음 순서에 따라 구조물을 만들었습니다.
- (1, 0)에서 위쪽으로 기둥을 하나 설치 후, (1, 1)에서 오른쪽으로 보를 하나 만듭니다.
- (2, 1)에서 위쪽으로 기둥을 하나 설치 후, (2, 2)에서 오른쪽으로 보를 하나 만듭니다.
- (5, 0)에서 위쪽으로 기둥을 하나 설치 후, (5, 1)에서 위쪽으로 기둥을 하나 더 설치합니다.
- (4, 2)에서 오른쪽으로 보를 설치 후, (3, 2)에서 오른쪽으로 보를 설치합니다.
만약 (4, 2)에서 오른쪽으로 보를 먼저 설치하지 않고, (3, 2)에서 오른쪽으로 보를 설치하려 한다면 2번 규칙에 맞지 않으므로 설치가 되지 않습니다. 기둥과 보를 삭제하는 기능도 있는데 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 합니다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.
벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성해주세요.
제한사항
- n은 5 이상 100 이하인 자연수입니다.
- build_frame의 세로(행) 길이는 1 이상 1,000 이하입니다.
- build_frame의 가로(열) 길이는 4입니다.
- build_frame의 원소는 [x, y, a, b]형태입니다.
- x, y는 기둥, 보를 설치 또는 삭제할 교차점의 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.
- a는 설치 또는 삭제할 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.
- b는 구조물을 설치할 지, 혹은 삭제할 지를 나타내며 0은 삭제, 1은 설치를 나타냅니다.
- 벽면을 벗어나게 기둥, 보를 설치하는 경우는 없습니다.
- 바닥에 보를 설치 하는 경우는 없습니다.
- 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제합니다.
- 구조물이 겹치도록 설치하는 경우와, 없는 구조물을 삭제하는 경우는 입력으로 주어지지 않습니다.
- 최종 구조물의 상태는 아래 규칙에 맞춰 return 해주세요.
- return 하는 배열은 가로(열) 길이가 3인 2차원 배열로, 각 구조물의 좌표를 담고있어야 합니다.
- return 하는 배열의 원소는 [x, y, a] 형식입니다.
- x, y는 기둥, 보의 교차점 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.
- 기둥, 보는 교차점 좌표를 기준으로 오른쪽, 또는 위쪽 방향으로 설치되어 있음을 나타냅니다.
- a는 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.
- return 하는 배열은 x좌표 기준으로 오름차순 정렬하며, x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬해주세요.
- x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오면 됩니다.
입출력 예
nbuild_frameresult| 5 | [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] | [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] |
| 5 | [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] | [[0,0,0],[0,1,1],[1,1,1],[2,1,1],[3,1,1],[4,0,0]] |
입출력 예에 대한 설명
입출력 예 #1
문제의 예시와 같습니다.
입출력 예 #2
여덟 번째 작업을 수행 후 아래와 같은 구조물 만들어집니다.
아홉 번째 작업의 경우, (1, 1)에서 오른쪽에 있는 보를 삭제하면 (2, 1)에서 오른쪽에 있는 보는 조건을 만족하지 않으므로 무시됩니다.
열 번째 작업의 경우, (2, 2)에서 위쪽 방향으로 기둥을 세울 경우 조건을 만족하지 않으므로 무시됩니다.
# 문제 해설 및 코드 리뷰
import java.util.Scanner;
class Solution{
static boolean[][] Pillar;
static boolean[][] Bar;
public int[][] solution(int n , int[][] build_frame){
Pillar = new boolean[n + 1][n + 1];
Bar = new boolean[n + 1][n + 1];
int count = 0;
for(int[] build : build_frame){
int x = build[0];
int y = build[1];
int type = build[2];
int cmd = build[3];
if(type == 0){
if(cmd == 1){
if(checkPillar(x, y)){
Pillar[x][y] = true;
count++;
}
}else{
Pillar[x][y] = false;
if(!canDelete(x, y)){
Pillar[x][y] = true;
}else
count--;
}
} else {
if(cmd == 1){
if(checkBar(x, y)){
Bar[x][y] = true;
count++;
}
}else{
Bar[x][y] = false;
if(!canDelete(x,y)){
Bar[x][y] = true;
}else
count--;
}
}
}
int[][] answer = new int[count][3];
count = 0;
for(int x = 0; x <= n; x++){
for(int y = 0; y <= n; y++){
if(Pillar[x][y]){
answer[count][0] = x;
answer[count][1] = y;
answer[count][2] = 0;
count++;
}
if(Bar[x][y]){
answer[count][0] = x;
answer[count][1] = y;
answer[count][2] = 1;
count++;
}
}
}
return answer;
}
static boolean checkPillar(int x, int y){
if(y == 0 || Pillar[x][y - 1])
return true;
if(x > 0 && Bar[x - 1][y])
return true;
if(Bar[x][y])
return true;
return false;
}
static boolean checkBar(int x, int y){
if(Pillar[x][y - 1])
return true;
if(x <= 100 && Pillar[x + 1][y - 1])
return true;
if(x > 0 && x <= 100 && Bar[x - 1][y] && Bar[x + 1][y])
return true;
return false;
}
static boolean canDelete(int x, int y){
for(int i = Math.max(x - 1, 0); i <= x + 1; i++){
for(int j = y; j <= y + 1; j++){
if(Pillar[i][j] && !checkPillar(i,j))
return false;
if(Bar[i][j] && !checkBar(i,j))
return false;
}
}
return true;
}
}구현 문제인데 난이도가 굉장히 까다로웠습니다.
정답률이 1. 중반대 퍼센트를 보여주더라구요..
그래서 전 유튜브 영상으로 해설을 보고 이렇게 포스팅을 통해 최대한 이해를 하려고 노력했습니다.
같이 한 번 살펴봅시다.
Pillar = new boolean[n + 1][n + 1];
Bar = new boolean[n + 1][n + 1];boolean타입의 배열은 2개 선언합니다.
Pillar는 기둥, Bar는 보를 뜻하는 배열로서 왜 2개를 선언하냐면 각 인덱스에 값이 2개 존재할 수 있기 때문입니다.
저는 처음에 구현할 때 한 개의 arr만 가지고 구현해보려 했는데 도저히 안되더라구요.
for(int[] build : build_frame){
int x = build[0];
int y = build[1];
int type = build[2];
int cmd = build[3];이후 for문을 통해 build_fram의 열은 4개이기 때문에 [x, y, type, cmd] 총 4가지를 각 변수에 받아옵니다.
예제의 input 데이터를 보면 x와 y를 시계 방향으로 90도 꺾은 것인데, 이를 무시하고 그대로 배열에 넣어도 무관합니다.
if(type == 0){
if(cmd == 1){
if(checkPillar(x, y)){
Pillar[x][y] = true;
count++;
}
}else{
Pillar[x][y] = false;
if(!canDelete(x, y)){
Pillar[x][y] = true;
}else
count--;
}type이 0이라면 기둥, 그리고 1이라면 보를 설치합니다.
일단 보를 설치할 경우는 나중에 살펴보도록 하고 여기서 한 번 더 분기를 해주셔야 합니다.
cmd가 1이면 설치, cmd가 0이라면 제거를 할 것입니다.
따라서 type이 0이고 cmd가 1일 때에 어떻게 프로그래밍되어야 하는지 살펴봅시다.
if(checkPillar(x, y)){
Pillar[x][y] = true;만약 checkPillar가 참이라면 Pillar[x][y]를 true로 바꿀 것입니다.
checkPillar함수는 기둥을 설치할 수 있는지 여부입니다.
그 여부는 어떻게 생겼는지 봅시다.
static boolean checkPillar(int x, int y){
if(y == 0 || Pillar[x][y - 1])
return true;
if(x > 0 && Bar[x - 1][y])
return true;
if(Bar[x][y])
return true;
return false;
}이렇게 생겼습니다.
만약 y가 0이라면 바닥이기 때문에 설치가 가능하고 Pillar[x][y - 1]이 true일 대에도 설치가 가능합니다.
이외에도 보를 기준으로 Bar[x - 1][y]일 때에 설치가 가능합니다.
왼쪽에서 보를 연결하면 좌에서 우로 연결이 되기 때문에 x - 1인덱스의 위치에서 연결할 때에는 설치가 가능한 것이지요.
하지만 x가 0일 때를 제외하고 설치가 가능한데, 왜냐하면 x가 0일 땐 시계 방향으로 90도 돌렸을 때 x - 1하면 음수가 되기 때문입니다.
뿐만 아니라 Bar[x][y]가 x, y의 위치에서 설치되어 있을때. 그러니까 보가 설치되어 있을 때에도 기둥이 설치가 가능합니다.
왜 하필 보가 설치 되어 있을 때 기둥이 설치 가능하다고 얘기하는걸까요?
굳이 이 분기가 필요할까요?
이런 궁금증을 해소하기 위해서 우선, 이 checkPillar함수의 의미를 알아야 합니다.
저희가 checkPillar함수를 통해 분기하고 싶은건 true를 찾는다는 의미도 맞겠지만 다르게 표현하자면 false를 거른다는 얘기와도 같습니다.
Bar배열과 Pillar배열을 저흰 나눠서 사용하고 있는데, 만약 Bar[x][y]가 참일 때를 고려해주지 않는다면 이것 또한 false가 되기 때문에 문제에 오류가 발생하게 됩니다.
이 함수를 통해 나타내고자 하는건, true가 되는 조건들을 모두 찾아서 나머지는 싹다 false로 보내고자 하는 것이 목표입니다.
이해가 가시나요?
그렇기 때문에 Bar[x][y]가 참일 때에도 빼먹으면 안되겠습니다.
다시 위로 올라갑니다.
만약 type이 1일 때를 살펴보겠습니다.
이것 또한 checkBar함수를 사용하여 보가 설치 가능한지 알아볼텐데요. 함수를 보겠습니다.
static boolean checkBar(int x, int y){
if(Pillar[x][y - 1])
return true;
if(x <= 100 && Pillar[x + 1][y - 1])
return true;
if(x > 0 && x <= 100 && Bar[x - 1][y] && Bar[x + 1][y])
return true;
return false;
}보가 설치 가능할 때에는 문제에서 어떤 설명을 하고 있는지 봅시다.
- 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
한쪽 끝 부분이 기둥 위에 있거나 -> Pillar[x][y - 1]가 true일 때 true!
Pillar[x + 1][y - 1]이 true이면서 x가 100보다 작거나 같을 때 -> 오른쪽 아래 기둥이 true일 때(Pillar)
마지막으로 Bar의 왼쪽 기둥과 오른쪽 기둥이 모두 참이고 x가 0과 100사이일때 true를 리턴하고 나머진 false를 보냅니다.
지금까지가 설치에 관한 구문이고 이젠 삭제에 대해 살펴보겠습니다.
삭제는 cmd가 0일 때인데 내용을 한 번 봅시다.
}else{
Pillar[x][y] = false;
if(!canDelete(x, y)){
Pillar[x][y] = true;
}else
count--;
}먼저 Pillar[x][y] 를 false로 바꾸어 줍시다.
이후 canDelete함수가 false이면 Pillar를 다시 true로 복원시키고 아니면 삭제가 가능하므로 그대로 삭제가 될 것입니다.
또한 이 때에는 count를 감소시킵니다.
static boolean canDelete(int x, int y){
for(int i = Math.max(x - 1, 0); i <= x + 1; i++){
for(int j = y; j <= y + 1; j++){
if(Pillar[i][j] && !checkPillar(i,j))
return false;
if(Bar[i][j] && !checkBar(i,j))
return false;
}
}
return true;
}canDelete함수는 다음과 같습니다.
이중 for문으로 총 6가지 주변 인덱스에 대해 탐색해봅시다.
만약 Pillar[i][j]가 true이고 checkPillar(i,j)가 false일 때.. 그러니까 기둥이 지금 설치되어 있으면서 기둥을 설치할 수 없을 때 그 때엔 삭제할 수 없겠죠?
따라서 false를 리턴하여 다시 Pillar 또는 Bar를 true로 바꿉니다.
그러니까 기둥을 삭제하려고 하는데, 만약 이 기둥을 제거했다가 건물이 무너질 수 있다는 상상을 해보세요.
그러면 무턱대고 삭제했다간 큰일 날 것입니다.
문제의 조건을 보면 기둥과 보를 삭제하는 기능도 있는데 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 합니다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.
이걸 보시면 삭제한 후에도 주변의 모든 기둥과 보들이 checkPillar와 checkBar를 만족해야 한다고 설명하고 있습니다.
왜 이중 for문에서 y의 범위는 y부터 y + 1까지일까요?
왜 x는 x - 1부터 x + 1까지일까요?
자, 만약 기둥이 3개 연속 연결되어 있다고 가정해보겠습니다.
이 중 기둥의 중간 것을 뽑는다 해볼게요.
그럼 어떻게 되나요? 위에 있는 기둥이 더 이상 있을 이유가 없겠죠?
그런데 이 기둥이 중간 기둥에 의해서 있는 것인지 아니면 외부의 다른 기둥이나 보에 의해서 있는 것인지 알 필요가 있습니다.
따라서
if(Pillar[i][j] && !checkPillar(i,j))
return false;
if(Bar[i][j] && !checkBar(i,j))
return false;이 구문을 통해, Pillar가 true이고 checkPillar가 false일 때.
기둥이 존재하며 방금 삭제한 기둥으로 인해 더 이상 윗칸의 기둥을 설치할 수 없을 때 false를 리턴하여 다시 Pillar를 복원합니다.
그리고 아무 이상 없으면 그대로 false로 남겨두고 count를 1 감소합니다.
이렇게 해서 count를 모두 세고
int[][] answer = new int[count][3];
count = 0;2차원 배열의 answer함수를 생성합니다.
count를 0으로 바꾼 뒤
for(int x = 0; x <= n; x++){
for(int y = 0; y <= n; y++){
if(Pillar[x][y]){
answer[count][0] = x;
answer[count][1] = y;
answer[count][2] = 0;
count++;
}
if(Bar[x][y]){
answer[count][0] = x;
answer[count][1] = y;
answer[count][2] = 1;
count++;
}
}
}
return answer;만약 기둥이 있으면 x, y, 0을 담고 count를 1 증가,
보가 있으면 x,y,1을 담고 count를 1 증가 하여 answer를 return하면 되겠습니다.
너무나도 어려운, 제가 풀어본 것 중 가장 섬세하고 낚시성 있는 문제였습니다.
나중에 다시 풀어봐야할 것 같아요. 다시 풀어보면 분명 잘 풀 수 있을 것 같은데 .. 해설을 보면 와 이거 내 것으로 만들 수 있을 것 같은데 막상 새로운 문제를 접하면 어렵고 새로운 것들이 많습니다.
Level 3 문제라 더 그런걸까요. 카카오 기출은 역시 쉽지 않네요.
감사합니다.
'프로그래머스 문제 풀이' 카테고리의 다른 글
| 프로그래머스 코딩테스트 연습 - 가장 먼 노드 (다익스트라, 플로이드-와샬, DFS) (0) | 2022.07.20 |
|---|---|
| 프로그래머스 코딩테스트 연습 - 합승 택시 요금 (플로이드-와샬, 다익스트라) (0) | 2022.07.18 |
| 프로그래머스 코딩테스트 연습 - 불량 사용자 (백트래킹, 정규식) (0) | 2022.07.12 |
| 프로그래머스 코딩테스트 연습 - 자물쇠와 열쇠 (구현, 배열) (0) | 2022.07.09 |
| [프로그래머스 Kit 풀이] Level 3 - 다단계 칫솔 (재귀) (0) | 2022.07.08 |
