2020 KAKAO BLIND RECRUITMENT - 기둥과 보 설치

2020 KAKAO BLIND RECRUITMENT - 기둥과 보 설치

https://programmers.co.kr/learn/courses/30/lessons/60061

접근

효율성 테스트도 하지 않고, 특별한 조건이 없기 때문에 시뮬레이션 위주의 문제라고 생각했습니다.
후반부에 배치된 문제이고, 프로그래머스 레벨도 다른문제보다 높아서 살짝 쫄았는데,
삼성 스타일의 문제를 많이 풀어서 그런지 어려움은 없었습니다.

항상 카카오 문제는 효율성 테스트가 없더라도 내 마음대로 하면 안될 것 같은 생각이 있었는데 이 문제 만큼은 깊게 생각 안하고 풀어도 성공했습니다.

1. 좌표 문제
   2차원 배열은 좌측 상단부터 0씩 증가하는 일반적인 형태로 생각하기 마련인데, 이 문제는 좌측 하단부터 증가하는 2차원 좌표 평면의 형태입니다. 특히 x,y를 r,c로 볼지 c,r로 봐야할지 하는 문제는 시뮬레이션에서 항상 머리를 아프게 합니다.
   다만 이번 문제는 굳이 배열을 선언하지 않고 풀었습니다. 어차피 해당 위치에 기둥이나 보가 있는지만 판단하면 되는 문제이기에 오히려 배열을 쓰면 더 복잡해질 것이라 생각했습니다.
   따라서 map에 key로 x,y좌표를, value로는 기둥과 보의 설치유무를 값으로 가지는 길이가 2인 배열을 담았습니다.
   

2. 조건 판단
   원래 그나마 가장 까다로운 부분을 꼽자면 삭제일것 같습니다. 하나를 삭제하면 왼쪽,오른쪽,위,아래,자기자리 이 5가지 영역에 영향을 미치기때문에 인접한 부분을 모두 조건판단해야 한다고 생각했는데, 사실 전체적인 크기가 작아서 그냥 삭제할때마다 지금 설치된 구조물들이 모두 조건에 부합하는지 검사했습니다.
   기둥일 경우 : 그 위치 아래가 바닥 or 그 위치에 보가 설치 or 그 위치 왼쪽에 보가 설치or 그 위치 아래가 기둥
   이라면 조건에 부합한다고 하였고
   보 일경우: 그 위치 아래가 기둥 or 그 위치 오른쪽 아래가 기둥 or 그 위치 왼쪽 오른쪽 모두 보가 설치 일 경우 조건에 부합한다고 판단했습니다.

3. 설치와 삭제
   그냥 설치면 설치하고 그 위치에 대하여 조건판단, 삭제일경우 삭제하고 전체 조건판단 후 부합하지 않으면 삭제 취소로 했습니다.

   다음은 코드 전문입니다.

  #include <string>
#include <vector>
#include <map>
#include <utility>
#include <string.h>
#include <algorithm>

using namespace std;

map<pair<int,int>, int[2] >info;

bool check(int x,int y,int kind);
bool cmp(vector<int> a,vector<int> b);
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    
    
    for(int i = 0 ; i < n+1 ; i++){
        for(int j = 0 ; j <n+1 ; j++){
            info[pair<int, int>(i,j)][0] = 0;
            info[pair<int, int>(i,j)][1] = 0;
        }
    }
    
    for(int i = 0 ; i < build_frame.size(); i++){
        if (build_frame[i][3] == 1) { //insert
            info[pair<int, int>(build_frame[i][0],build_frame[i][1])][build_frame[i][2]] = 1;
            if(check(build_frame[i][0], build_frame[i][1], build_frame[i][2])){ //possible insert
                
            }else{//impossible
                info[pair<int, int>(build_frame[i][0],build_frame[i][1])][build_frame[i][2]] = 0;
            }
            
        }else{ //delete
            
            info[pair<int, int>(build_frame[i][0],build_frame[i][1])][build_frame[i][2]] = 0;
            bool isDeletable = true;
            for(map<pair<int,int>, int[2] >::iterator iter = info.begin() ; iter != info.end(); ++iter){ //all direction that effected by delete
                if (iter->second[0] == 0 && iter->second[1] == 0) {
                    continue;
                }
                else{ //
                    if (iter->second[0]  && !(check(iter->first.first, iter->first.second, 0))) {
                        isDeletable = false;
                        break;
                    }
                    if (iter->second[1]  && !(check(iter->first.first, iter->first.second, 1))) {
                        isDeletable = false;
                        break;
                    }
                }
            }
            if (!isDeletable) {
                info[pair<int, int>(build_frame[i][0],build_frame[i][1])][build_frame[i][2]] = 1;
            }
            
        }
    }
    
    vector<int> temp(3,0);
    for(map<pair<int,int>, int[2] >::iterator iter = info.begin() ; iter != info.end(); ++iter){
        if (iter->second[0] == 0 && iter->second[1] == 0) {
            continue;
        }else if (iter->second[0] == 1 && iter->second[1] == 1) {
            
            temp[0] = iter->first.first;
            temp[1] = iter->first.second;
            temp[2] = 0;
            answer.push_back(temp);
            temp[2] = 1;
            answer.push_back(temp);
        }else{
            temp[0] = iter->first.first;
            temp[1] = iter->first.second;
            if (iter->second[0] == 1) {
                temp[2] = 0;
            }else if(iter->second[1] == 1){
                temp[2] = 1;
            }
            
            answer.push_back(temp);
        }
    }
    sort(answer.begin(), answer.end(), cmp);
    return answer;
}

bool check(int x,int y,int kind){
    
    if (kind == 0) { //column
        if (y == 0) { //is floor
            return true;
        }else if(info[pair<int, int>(x,y)][1] == 1){ // is bow from rifgt
            return true;
        }else if(info[pair<int, int>(x-1,y)][1] == 1){ //is bow from left
            return true;
        }else if(info[pair<int, int>(x,y-1)][0] == 1){ // is upper from column
            return true;
        }
        
        
        
        
    }else{ //bow
        if(info[pair<int, int>(x,y-1)][0] == 1){ // is upper from column
            return true;
        } else if(info[pair<int, int>(x+1,y-1)][0] == 1){ // is upper from column(right-down)
            return true;
        } else if(info[pair<int, int>(x-1,y)][1] == 1 && info[pair<int, int>(x+1,y)][1] == 1){ // between bow
            return true;
        }
        
        
    }
    return false;
}

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

후기

2시간 정도 걸렸습니다. 실제 테스트에서 마주치면 시간이 모자를 수 있을것 같아 빨리 작성하는 연습을 해보아야겠습니다.

그리고 마지막 1시간쯤은 같은 좌표에 기둥과 보가 동시에 설치되어있는 경우를 고려하지않고 answer에 넣어서 계속 실패가 나왔습니다.

조금만 신경썼으면 시간을 단축 가능한 부분이었습니다.