기둥과 보 설치 (C++) 2020 KAKAO BLIND RECRUITMENT

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

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

 

0. 문제 개요

두 종류의 구조물이 있고, (기둥, 보)

두 종류의 동작이 있다. (설치, 삭제)

또한 각 구조물은 다음과 같은 조건을 만족해야 한다.

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

구조물, 동작이 쿼리로 주어지면 그것을 처리하고 난 뒤 결과물을 정렬해서 출력한다.

 

 

 

 

1. 문제 해결 아이디어

1-1. 구조물이 겹칠 수 있으므로 기둥과 보 배열을 따로 저장한다.

1-2. 구조물이 조건을 만족하는지 확인하는 함수를 구현한다.

1-3. 설치는 설치 전에 1-2 함수를 만족하는지 확인한다. 삭제는 삭제 후 현재 존재하는 구조물이 1-2 함수를 만족하는지 확인한다.

 

 

2. 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
int gmap[101][101], bmap[101][101];
 
bool cmp(vector<int> p1, vector<int> p2) {
    
    if (p1[0] == p2[0]) {            //x좌표가 같다면
        if (p1[1] == p2[1]) {        //y좌표까지 같다면
            return p1[2] < p2[2];    //기둥이 먼저 오도록 함
        }
        return p1[1] < p2[1];        //x좌표가 같으면 y좌표 오름차순으로 정렬
    }
    return p1[0] < p2[0];            //1순위로 x좌표로 정렬
}
 
int possible(int px, int py, int type, int n) {
    int flag = 0;
    if (type == 0) {
        //기둥 가능 여부 체크
        if (py == 0 || gmap[py - 1][px]
            || bmap[py][px] || bmap[py][px-1] ) {
            return 1;
        }
        return 0;
        
    }
    else {
        //보 가능 여부 체크
        if (gmap[py - 1][px] || gmap[py - 1][px + 1] ||  (
            bmap[py][px - 1] && bmap[py][px + 1] ))
            return 1;
 
        return 0;
 
    }
}
 
 
void build(int px, int py, int type, int n) {
 
    if (type == 0) {
        //기둥 설치
        if (possible(px, py, 0, n)) {
            gmap[py][px] = 1;
        }
    }
    else {
        //보 설치
        if (possible(px, py, 1, n)) {
            bmap[py][px] = 1;
        }
    }
 
}
 
void destroy(int px, int py, int type, int n) {
 
    if (type == 0) {
        //기둥
        gmap[py][px] = 0;        //기둥을 일단 삭제해본다.
        int flag = 0;
        for (int i = 0;i <= n;i++) {
            for (int j = 0;j <= n;j++) {
                //기둥 삭제 후 나머지 기둥, 보가 온전한지 확인
                if (gmap[i][j]) {
                    if ( !possible(j, i, 0,n)) {
                        flag = -1;
                    }
                    
                }
                if (bmap[i][j]) {
                    if (!possible(j, i, 1,n)) {
                        flag = -1;
                    }
                
                }
            }
        }
        if (flag == -1) {    //하나라도 온전하지 않으면
            gmap[py][px] = 1;    //삭제했던 기둥을 복원
        }
    }
    else {
        //보
        bmap[py][px] = 0;
        //일단 보를 삭제해본다.
        int flag = 0;
        //나머지 보에 대해 유효성 검사
        for (int i = 0;i <= n;i++) {
            for (int j = 0;j <= n;j++) {
                if (gmap[i][j]) {
                    if (!possible(j, i, 0,n)) {
                        flag = -1;
                    }
                }
                if (bmap[i][j]) {
                    if (!possible(j, i, 1,n)) {
                        flag = -1;
                    }
                }
            }
        }
        //하나라도 유효하지 않으면 
        if (flag == -1) {
            //보를 원상복구
            bmap[py][px] = 1;
        }
    }
 
}
 
 
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    int px, py, type, opt;
    vector<vector<int>> answer;
    for (vector<int> query : build_frame) {
        px = query[0];
        py = query[1];
        type = query[2];
        opt = query[3];
        if (opt == 1) {
            build(px, py, type,n);
        }
        else {
            destroy(px, py, type, n);
        }
    }
    
    for (int i = 0;i <= n;i++) {                //기둥과 보 정보를 answer에 저장한다.
        for (int j = 0;j <= n;j++) {
            if (gmap[i][j]) {
                answer.push_back({ j,i,0 });
            }
            if (bmap[i][j]) {
                answer.push_back({ j,i,1 });
            }
        }
    }
    sort(answer.begin(), answer.end(), cmp);        // answer를 정렬
 
 
    return answer;
 
}
 

 

3. 나가며... (삽질한 내용)

예제 테케는 통과하는데 채점하면 하나도 통과를 못했다..

알고 보니 정렬(cmp 함수)이 문제였다.

cmp 함수를 수정하니 통과되었다. 낮은 우선순위부터 정의하는 위 방식을 잘 익혀두자.