(C++) - 프로그래머스(2020 KAKAO BLIND RECRUITMENT) : 기둥과 보 설치

https://programmers.co.kr/learn/courses/30/lessons/60061?language=cpp 

코딩테스트 연습 - 기둥과 보 설치

구현 문제였습니다.

 

풀이방법

 set을 이용해 해결했습니다.

 

 1. 전체 로직 : 매 build_frame마다 set에 {x,y,종류(기둥 또는 보)}를 설치 또는 삭제를 한 뒤 isValud함수를 통해 유효한 명령인지 확인합니다. 그 후 유효하지 않다면 원복해줍니다.

 

 2. 유효 검사 : set에 들어있는 즉, 현재 설치된 구조물들 전체에 대해 다음 로직을 수행합니다. 먼저 설치 또는 삭제하기 때문에 전체구조가 알맞는지 검사하기 위함입니다. 기둥인 경우와 보인 경우 로 나위며 검사로직이 달라집니다.

  2-1. 현재 확인하는 구조물이 기둥인 경우 : 바닥에 설치된 경우, 바로 아래에 기둥이 있는 경우, 왼쪽에 보가 있는 경우, 오른쪽에 보가 있는 경우 유효한 구조입니다. 

 

  2-2. 보인 경우 : 왼쪽 끝 점이 보의 시작점이므로 바로 아래에 기둥이 있거나 우하에 해당하는 곳에 기둥이 있거나 왼쪽, 오른쪽 둘 다 보가 설치되어 있는 구조일 경우 유효합니다.

 

 3. answer 반환 : set의 원소를 answer에 넣어 규칙에 따라 정렬해 return 해줍니다.

Code

 

#include <bits/stdc++.h>
using namespace std;

bool cmp(vector <int> &a, vector <int> &b){
    if(a[0] == b[0]){
        if(a[1] == b[1]) return a[2] < b[2];
        return a[1] < b[1];
    }
    return a[0] < b[0];
}

bool isValid(set <vector<int>> ckSet){
    for(auto s : ckSet){
        vector <int> tmp = s;
        int x = tmp[0];
        int y = tmp[1];
        int cat = tmp[2];
        //기둥이면 : 아래 바닥, 아래 기둥, 왼쪽 보, 오른쪽 보일 떄 ok
        if(!cat) {
            if(y == 0 || ckSet.find({x,y-1,0}) != ckSet.end() || ckSet.find({x-1,y,1}) != ckSet.end() || ckSet.find({x,y,1}) != ckSet.end()) continue;
            else return false;
        }
        //보면 : 아래 기둥, 우하 기둥, (왼보와 오른보) 존재할 때 ok
        else{
            if(ckSet.find({x,y-1,0}) != ckSet.end() || ckSet.find({x + 1, y - 1,0}) != ckSet.end() || (ckSet.find({x-1,y,1}) != ckSet.end() && ckSet.find({x+1,y,1}) != ckSet.end())) continue;
            else return false;
        }
    }
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    vector<vector<int>> board(n+1,vector<int>(n+1,0));
    set <vector<int>> ckSet;

    for(int i = 0; i < build_frame.size(); i++){
        int col = build_frame[i][0];
        int row = build_frame[i][1];
        int cat = build_frame[i][2];
        int install = build_frame[i][3];

        if(install){
            ckSet.insert({col,row,cat});
            if(!isValid(ckSet)) ckSet.erase({col,row,cat});
        }

        else{
            ckSet.erase({col,row,cat});
            if(!isValid(ckSet)) ckSet.insert({col,row,cat});
        }
    }

    for(auto c : ckSet){
        vector <int> tmp = c;
        int x = tmp[0];
        int y = tmp[1];
        int cat = tmp[2];
        answer.push_back({x, y, cat});
    }

    sort(answer.begin(),answer.end(),cmp);
    return answer;
}