[프로그래머스/c++, java] 기둥과 보 설치

카카오 Lv3 문제라 쉽지 않을거라고 예상했지만

역시나 어려웠다

🤯

 

---

처음 푼 방식의 경우,

주어진 테스트 케이스 두개는 통과했지만 채점 시에 맞는 테스트 케이스가 단 하나도 없었다ㅎ

 

 

설치와 삭제하는 케이스 모두 일일이 점검하면서 풀었지만, 아마 내가 생각하지 못한 케이스들이 많은 것 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct FrameInfo{
    int x, y, a;
    
    FrameInfo(int x, int y, int a){
        this->x=x;
        this->y=y;
        this->a=a;
    }
};

int compare(FrameInfo f1, FrameInfo f2){
    if(f1.x!=f2.x){
        return f1.x<f2.x;
    } else{
        if(f1.y!=f2.y){
            return f1.y<f2.y;
        } else{
            return f1.a<f2.a;
        }
    }
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    vector<FrameInfo> frameInfos;
    
    for(int j=0; j<build_frame.size(); j++){
        int x=build_frame[j][0], y=build_frame[j][1];
        int a=build_frame[j][2], b=build_frame[j][3];
        
        if(b==1){ // 설치하는 경우
            if(a==0){ // 기둥 설치
                if(y==0){
                    frameInfos.push_back(FrameInfo(x, y, a));
                } else{
                    for(int i=0; i<frameInfos.size(); i++){
                        if(frameInfos[i].x==x && frameInfos[i].y==y-1 && frameInfos[i].a==0){
                            frameInfos.push_back(FrameInfo(x, y, a));
                            break;
                        } else if(frameInfos[i].x+1==x && frameInfos[i].y==y && frameInfos[i].a==1){
                            frameInfos.push_back(FrameInfo(x, y, a));
                            break;
                        }
                    }
                }
            } else if(a==1){ // 보 설치
                // 한쪽 끝이 기둥 위에 있는 경우
                for(int i=0; i<frameInfos.size(); i++){
                    if(frameInfos[i].x==x && frameInfos[i].y+1==y 
                       && frameInfos[i].a==0){ // 왼쪽 끝
                        frameInfos.push_back(FrameInfo(x, y, a));
                        break;
                    } else if(frameInfos[i].x==x+1 && frameInfos[i].y+1==y 
                              && frameInfos[i].a==0) { // 오른쪽 끝
                        frameInfos.push_back(FrameInfo(x, y, a));
                        break;
                    }
                }
                // 양쪽 끝이 보와 연결되는 경우
                int bo=0;
                for(int i=0; i<frameInfos.size(); i++){
                    if(frameInfos[i].x+1==x && frameInfos[i].y==y && frameInfos[i].a==1){
                        bo++;
                    }
                    if(frameInfos[i].x-1==x && frameInfos[i].y==y && frameInfos[i].a==1){
                        bo++;
                    }
                }
                if(bo==2){
                    frameInfos.push_back(FrameInfo(x, y, a));
                }
            }
        } else if(b==0){ // 삭제하는 경우
            if(a==0){ // 기둥 삭제
                int bo=0, idx;
                // 밑이나 위에 기둥 있으면 삭제 못함
                int gidong=0;
                // 밑이나 위에 기둥 없으면 위에 양쪽으로 보가 있거나 없는 경우 삭제 가능
                for(int i=0; i<frameInfos.size(); i++){
                    if(frameInfos[i].x==x && frameInfos[i].y+1==y && frameInfos[i].a==0){
                        gidong++;
                        break;
                    }
                    if(frameInfos[i].x==x && frameInfos[i].y-1==y && frameInfos[i].a==0){
                        gidong++;
                        break;
                    }
                    if(frameInfos[i].x==x && frameInfos[i].y==y+1 && frameInfos[i].a==1){
                        bo++;
                    }
                    if(frameInfos[i].x==x-1 && frameInfos[i].y==y+1 && frameInfos[i].a==1){
                        bo++;
                    }
                    if(frameInfos[i].x==x && frameInfos[i].y==y && frameInfos[i].a==a){
                        idx=i;
                    }
                }
                if(gidong==0 && (bo==0 || bo==2)){
                    frameInfos.erase(frameInfos.begin()+idx, frameInfos.begin()+idx+1);
                }
            } else if(a==1){ // 보 삭제
                // 보 위에 기둥이 있으면 삭제 못함
                int gidong=0;
                for(int i=0; i<frameInfos.size(); i++){
                    if(frameInfos[i].x==x && frameInfos[i].y==y && frameInfos[i].a==0){
                        gidong++;
                        break;
                    } else if(frameInfos[i].x==x+1 && frameInfos[i].y==y && frameInfos[i].a==0){
                        gidong++;
                        break;
                    }
                }
                // 그 중에서 보 사이에 낀 보만 삭제 가능
                if(gidong==0){
                    int bo=0, leftGidong=0, rightGidong=0, idx;
                    for(int i=0; i<frameInfos.size(); i++){
                        if(frameInfos[i].x==x-1 && frameInfos[i].y==y && frameInfos[i].a==1){
                            bo++;
                        }
                        if(frameInfos[i].x==x+1 && frameInfos[i].y==y && frameInfos[i].a==1){
                            bo++;
                        }
                        if(frameInfos[i].x==x-1 && frameInfos[i].y==y-1 && frameInfos[i].a==0){
                            leftGidong++;
                        }
                        if(frameInfos[i].x==x+2 && frameInfos[i].y==y-1 && frameInfos[i].a==0){
                            rightGidong++;
                        }
                        if(frameInfos[i].x==x && frameInfos[i].y==y && frameInfos[i].a==a){
                            idx=i;
                        }
                    }
                    if(leftGidong==1 && rightGidong==1 && bo==2){
                        frameInfos.erase(frameInfos.begin()+idx, frameInfos.begin()+idx+1);
                    }
                }
            }
        }        
    }
    
    sort(frameInfos.begin(), frameInfos.end(), compare);
    for(int i=0; i<frameInfos.size(); i++){
        vector<int> frameInfo;
        frameInfo.push_back(frameInfos[i].x);
        frameInfo.push_back(frameInfos[i].y);
        frameInfo.push_back(frameInfos[i].a);
        answer.push_back(frameInfo);
    }
    
    
    
    return answer;
}

 

일단 우선, 2차원 배열을 통해 기둥과 보의 위치를 표시하는 걸로 변경했다.

설치의 경우, 기존과 동일하게 조건에 맞으면 설치하도록 하였고

삭제의 경우, 우선 삭제한 후에 배열을 점검하여 삭제가 가능하다면 그대로 삭제해두고,

삭제가 불가능하다면 다시 복원하도록 구현했다.

 

c++

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<vector<int>>> map(101, vector<vector<int>>(101, vector<int>(2, 0)));
int N;

bool isValidGidung(int x, int y){
    // 바닥, 보 왼쪽 위, 보 오른쪽 위, 다른 기둥 위
    if(y==0) return true;
    else if(map[x][y][1]==1) return true;
    else if(x-1>=0 && map[x-1][y][1]==1) return true;
    else if(y-1>=0 && map[x][y-1][0]==1) return true;
    else return false;
}

bool isValidBo(int x, int y){
    // 보 왼쪽이 기둥 위, 보 오른쪽이 기둥 위, 양쪽 끝이 보와 연결
    if(y-1>=0 && map[x][y-1][0]==1) return true;
    else if(x+1<=N && y-1>=0 && map[x+1][y-1][0]==1) return true;
    else if(x-1>=0 && x+1<=N && map[x-1][y][1]==1 && map[x+1][y][1]==1) return true;
    else return false;
}

bool isValidMap(){
    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            if(map[i][j][0]==1) // 기둥
                if(!isValidGidung(i, j)) return false;
            if(map[i][j][1]==1) // 보
                if(!isValidBo(i, j)) return false;
        }
    }
    
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    N=n;
    
    for(int i=0; i<build_frame.size(); i++){
        int x=build_frame[i][0], y=build_frame[i][1];
        int a=build_frame[i][2], b=build_frame[i][3];
        
        if(b==1){ // 설치
            if(a==0){ // 기둥 설치
                if(isValidGidung(x, y))
                    map[x][y][a]=1;
            } else if(a==1){ // 보 설치
                if(isValidBo(x, y))
                    map[x][y][a]=1;
            }
        } else if(b==0){ // 삭제
            map[x][y][a]=0; // 삭제
            if(!isValidMap()){ // 점검, 유효한 Map이 아닌 경우 복원
                map[x][y][a]=1;
            }
        }        
    }
    
    for(int i=0; i<=n; i++){
        for(int j=0; j<=n; j++){
            if(map[i][j][0]==1){
                answer.push_back(vector<int>{i, j, 0});
            }
            if(map[i][j][1]==1){
                answer.push_back(vector<int>{i, j, 1});
            }
        }
    }
    
    return answer;
}

 

 

Java

import java.util.*;

class Solution {
    private int[][][] map = new int[101][101][2];
    private int N;
    
    private boolean isValidGidung(int x, int y){
        // 바닥, 보 왼쪽 위, 보 오른쪽 위, 다른 기둥 위
        if(y==0) return true;
        else if(map[x][y][1]==1) return true;
        else if(x-1>=0 && map[x-1][y][1]==1) return true;
        else if(y-1>=0 && map[x][y-1][0]==1) return true;
        else return false;
    }

    private boolean isValidBo(int x, int y){
        // 보 왼쪽이 기둥 위, 보 오른쪽이 기둥 위, 양쪽 끝이 보와 연결
        if(y-1>=0 && map[x][y-1][0]==1) return true;
        else if(x+1<=N && y-1>=0 && map[x+1][y-1][0]==1) return true;
        else if(x-1>=0 && x+1<=N && map[x-1][y][1]==1 && map[x+1][y][1]==1) return true;
        else return false;
    }

    private boolean isValidMap(){
        for(int i=0; i<=N; i++){
            for(int j=0; j<=N; j++){
                if(map[i][j][0]==1) // 기둥
                    if(!isValidGidung(i, j)) return false;
                if(map[i][j][1]==1) // 보
                    if(!isValidBo(i, j)) return false;
            }
        }

        return true;
    }
    
    public int[][] solution(int n, int[][] build_frame) {
        int[][] answer;
        int cnt=0;
        N=n;
        
        for(int i=0; i<build_frame.length; i++){
            int x=build_frame[i][0], y=build_frame[i][1];
            int a=build_frame[i][2], b=build_frame[i][3];

            if(b==1){ // 설치
                if(a==0){ // 기둥 설치
                    if(isValidGidung(x, y)){
                        map[x][y][a]=1;
                        cnt++;
                    }
                } else if(a==1){ // 보 설치
                    if(isValidBo(x, y)){
                        map[x][y][a]=1;
                        cnt++;
                    }
                }
            } else if(b==0){ // 삭제
                map[x][y][a]=0; // 삭제
                cnt--;
                if(!isValidMap()){ // 점검, 유효한 Map이 아닌 경우 복원
                    map[x][y][a]=1;
                    cnt++;
                }
            }   
        }
        
        answer = new int[cnt][3];
        int ansIdx=0;
        for(int i=0; i<=n; i++){
            for(int j=0; j<=n; j++){
                if(map[i][j][0]==1){
                    answer[ansIdx][0]=i;
                    answer[ansIdx][1]=j;
                    answer[ansIdx][2]=0;
                    ansIdx++;
                }
                if(map[i][j][1]==1){
                    answer[ansIdx][0]=i;
                    answer[ansIdx][1]=j;
                    answer[ansIdx][2]=1;
                    ansIdx++;
                }
            }
        }
        
        return answer;
    }
}

 

😀😲

3일 간의 삽질 끝에, 성공했다!

조건들이 많아 구현하기에 복잡한 문제였다

구현 후에, 함수 생성을 통해 코드 정리를 해보니 로직 이해가 쉬웠다 :)