구현
프로그래머스 2020 KAKAO BLIND RECRUITMENT Level 3 문제 기둥과 보 설치를 Java를 이용해 풀지 못했다. 느므 머리가 어지럽다. 구현 엿 같다. 띠밤
결국 다른 사람 풀이 보며 간신히 이해하고 따라 친 수준이었다. 가슴이 아프다...
문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/60061
힘으로 구현
아름다운 풀이로 WOW 를 외치게 하는 풀이 같은 건 없는 것 같다. 그냥 힘으로 욱여 푸는 느낌인 것 같다. 뭐 물론 다 이해하고 나니까 할 수 있었을 것 같은데...? 라는 생각은 들지만 그런 거슨 없다. 못 풀면 못 푼 거다! 띠밤!
항상 전수 조사하는 거에 대한 막연한 두려움이 있어서 선뜻 손가락이 움직이질 않는데, 이번 문제에서는 기둥 혹은 보를 제거할 수 있는지 확인할 때 전수 조사를 돌렸다. 이렇게 안 해도 조건 잘 맞춰 짜면 필요한 부분만 살펴보고도 제거 가능 여부를 알 수 있다고 하는데 나는 그렇게까지는 못하겠더라.
결국 가장 중요한 것은 특정 좌표에 기둥 혹은 보가 위치할 수 있는지를 확인해주는 것이다. 또한 (0,0)부터 (n,n)까지의 좌표를 모두 쓰기 때문에 new int[n][n]이 아닌 new int[n+1][n+1]의 사이즈 배열을 선언해주는 것도 신경 써주면 된다.
기둥 및 보 설치
특정 좌표에 기둥과 보가 존재할 수 있는지의 여부를 알려주는 checkKidoong(int x, int y)과 checkBo(int x, int y) 메소드를 만들었다.
static Boolean checkKidoong(int x, int y){
if(y==0) return true; // 바닥에 설치할 경우
else if((x>0 && bo[x-1][y]==1) || bo[x][y]==1) return true; // 그 자리에 보가 있을 경우
else if(y>0 && kidoong[x][y-1]==1) return true; // 아래 기둥이 있을 경우
else return false; // 싹 다 만족 못하면 무시
}
static Boolean checkBo(int x, int y){
if(y>0 && (kidoong[x][y-1]==1 || kidoong[x+1][y-1]==1)) return true; // 한 쪽에 기둥이 있을 때
else if(x>0 && bo[x-1][y]==1 && bo[x+1][y]==1) return true; // 양쪽에 보가 있을 때
else return false; // 싹 다 만족 못하면 무시
}특정 좌표를 넘겨줘서 그 좌표에 대해 주변 정보를 살펴서 넘겨준 좌표에 존재할 수 있으면 true, 아니면 false를 반환해주면 된다.
위의 두 메소드를 통해서 문제에서 제시된 build_frame 배열의 정보에 따라 설치를 진행해보자. 이를 코드로 표현하면 다음과 같다.
for(int[] info: build_frame){
switch(info[3]){ // 설치 or 삭제
case 0: // 삭제
...
case 1: // 설치
if(info[2]==0)
if(checkKidoong(info[0],info[1])) kidoong[info[0]][info[1]] = 1;
if(info[2]==1)
if(checkBo(info[0],info[1])) bo[info[0]][info[1]] = 1;
break;
}
}삭제는 나중에 살펴보고, 우선 설치부터 보면 위와 같이 누구를 설치해주냐에 따라서 두 가지 check 메소드를 선택해서 기둥 및 보를 설치해주면 된다.
기둥 및 보 제거
이번에는 제거 작업을 살펴보자. 제거를 위해서는 제거하라는 녀석을 없애본 후에 -> 제거된 상태가 온전한 상태인지 확인해보면 된다.
바로 여기서 전수 조사가 들어가는 것이다.
일단 제거를 때리고, 기둥과 보가 존재하는 모든 좌표를 돌며 온전한 형태인지 check 메소드를 통해서 확인해준 후에 만약 온전하지 않으면 false를 날리면 된다.
제거를 때리고 난 후에 온전한지 확인하는 작업이기 때문에 메소드 이름을 isStillOkay()로 지어줬다.
static Boolean isStillOkay(int n){
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++){
if(kidoong[i][j]==1 && !checkKidoong(i,j)) return false;
else if(bo[i][j]==1 && !checkBo(i,j)) return false;
}
}
return true;
}말 그대로 전수 조사다. 전체 지도 사이즈 값만 넘겨준 후에 앞서 선언한 check 메소드를 통해 모든 좌표에 대해 검사해주면 된다.
그럼 build_frame 배열에서 들어온 삭제 명령을 어떻게 처리하는지 위의 isStillOkay(int n) 메소드를 이용해서 살펴보자.
for(int[] info: build_frame){
switch(info[3]){ // 설치 or 삭제
case 0: // 삭제
if(info[2]==0)
kidoong[info[0]][info[1]] = 0; // 일단 날리고
if(!isStillOkay(n)) kidoong[info[0]][info[1]] = 1; // 안 괜찮으면 다시 주섬주섬 세워주자
if(info[2]==1)
bo[info[0]][info[1]] = 0; // 여기서도 일단 날리고
if(!isStillOkay(n)) bo[info[0]][info[1]] = 1; // 안 괜찮으면 다시 놓아주자
break;
case 1: // 설치
...기둥과 보 좌표 정렬
위에서의 작업으로 기둥과 보 설치 및 제거 작업은 모두 끝났다. 이제 문제에서 요구하는 순서대로 기둥과 보의 좌표를 정렬해주기만 하면 된다.
이건 뭐 간단하니까 별 설명없이 코드만 첨부하겠다.
ArrayList<int[]> list = new ArrayList<>();
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++){
if(kidoong[i][j]==1){
int[] tmpKidoong = { i, j, 0 };
list.add(tmpKidoong);
}
if(bo[i][j]==1){
int[] tmpBo = { i, j, 1 };
list.add(tmpBo);
}
}
}
int[][] answer = list.toArray(new int[list.size()][3]);
return answer;기둥이 들어가고 나서 보가 들어가야 하니까 그 순서만 위와 같이 배치해주면 된다.
아래는 내가 제출한 전체 코드다.
import java.io.*;
import java.util.ArrayList;
public class PillarConstruction {
static int[][] kidoong, bo;
static int[][] solution(int n, int[][] build_frame) {
kidoong = new int[n+1][n+1];
bo = new int[n+1][n+1];
for(int[] info: build_frame){
switch(info[3]){ // 설치 or 삭제
case 0: // 삭제
if(info[2]==0)
kidoong[info[0]][info[1]] = 0;
if(!isStillOkay(n)) kidoong[info[0]][info[1]] = 1;
if(info[2]==1)
bo[info[0]][info[1]] = 0;
if(!isStillOkay(n)) bo[info[0]][info[1]] = 1;
break;
case 1: // 설치
if(info[2]==0)
if(checkKidoong(info[0],info[1])) kidoong[info[0]][info[1]] = 1;
if(info[2]==1)
if(checkBo(info[0],info[1])) bo[info[0]][info[1]] = 1;
break;
}
}
ArrayList<int[]> list = new ArrayList<>();
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++){
if(kidoong[i][j]==1){
int[] tmpKidoong = { i, j, 0 };
list.add(tmpKidoong);
}
if(bo[i][j]==1){
int[] tmpBo = { i, j, 1 };
list.add(tmpBo);
}
}
}
int[][] answer = list.toArray(new int[list.size()][3]);
return answer;
}
static Boolean checkKidoong(int x, int y){
if(y==0) return true; // 바닥에 설치할 경우
else if((x>0 && bo[x-1][y]==1) || bo[x][y]==1) return true; // 그 자리에 보가 있을 경우
else if(y>0 && kidoong[x][y-1]==1) return true; // 아래 기둥이 있을 경우
else return false; // 싹 다 만족 못하면 무시
}
static Boolean checkBo(int x, int y){
if(y>0 && (kidoong[x][y-1]==1 || kidoong[x+1][y-1]==1)) return true; // 한 쪽에 기둥이 있을 때
else if(x>0 && bo[x-1][y]==1 && bo[x+1][y]==1) return true; // 양쪽에 보가 있을 때
else return false; // 싹 다 만족 못하면 무시
}
static Boolean isStillOkay(int n){
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++){
if(kidoong[i][j]==1 && !checkKidoong(i,j)) return false;
else if(bo[i][j]==1 && !checkBo(i,j)) return false;
}
}
return true;
}
public static void main(String[] args) throws IOException {
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = 5;
int[][] build_frame = { {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} };
int[][] result = solution(n, build_frame);
for(int[] line: result) bfw.write(line[0] + " " + line[1] + " " + line[2] + "\n");
bfw.close();
}
}오늘 배운 것
- 쌉구현 문제는 어렵다
- 어거지로라도 어떻게든 만들려고 집요하게 물고 늘어지자. 까다로워 보인다고 겁 먹고 주눅 들지말고!
