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

김영한·2021년 9월 7일
0

알고리즘

목록 보기
71/74

문제 링크 : 기둥과 보 설치

[문제 접근]

범위가 크지 않아서 브루트 포스로 접근했다.
하지만 예외처리를 많이 해줘야하는 상황이 발생해서 결국 풀지 못했고 다른 사람 코드를 참고했다.

참고한 코드의 아이디어는 추가 삭제시 마다 세워진 구조물들을 전부 탐색한다는 점에서 내가 푼 방향과 비슷하긴하지만 set을 이용해 풀어서 배열을 이용해 푸는 것보다 훨씬 쉽게 해결할 수 있었다.

map이 더 좋을 것 같다는 생각을 했는데 어차피 제한사항에서 중복 좌표는 없다고 나와있으니 더 빠른 Set이 효율적일 것 같다.

Set은 내부적으로 이진트리로 구성되어 있어서 삽입, 삭제가 Vector에 비해 빠르다. (logN 걸림)
순차 접근도 가능하고 삽입, 삭제 시 정렬된다.

주의할 점은 이 문제를 풀면서 나는 set의 자료형으로 구조체를 만들어서 사용했는데
구조체 사용시 정렬을 정의해줘야 set의 자료형으로 사용할 수 있다.
(일반적인 vector나 int, string을 자료형으로 가지면 기본적으로 오름차순으로 정렬되기 때문에 정의할 필요는 없다.)
(내가 만든 자료형을 사용할 때만 정렬을 정의해야한다.)
  • 기둥이 추가될 때
    • (x, y)에 기둥을 설치할 때 조건에 만족하려면
      1. (x, y)에 보가 설치되어 있거나
      2. (x-1, y)에 보가 설치되어 있거나
      3. (x, y-1)에 기둥이 설치되어 있거나
      4. y=0이여서 바닥이거나
  • 보가 추가될 때
    • (x, y)에 보를 설치할 때 조건에 만족하려면
      1. (x, y-1)에 기둥이 설치되어 있거나
      2. (x+1, y-1)에 기둥이 설치되어 있거나
      3. (x-1, y)에 보가 설치되어있으면서 (x+1, y)에 보가 설치되어 있거나
  • 삭제도 동일한 방법이다.

위 방식으로 추가나 삭제 시 조건에 모두 만족하면 그대로 진행하고 아니면 롤백하는 방식으로 구현하면 해결할 수 있다.

[소스 코드]

#include <string>
#include <vector>
#include <set>
using namespace std;

struct node {
    int x;
    int y;
    int st;
    
    bool operator < (const node& other) const { // 정렬을 정의
        if(x==other.x) {
            if(y==other.y) return st<other.st;
            return y<other.y;
        }
        return x<other.x;
    }
};
set<node> structures;

bool has(node temp) {
    return structures.find(temp)!=structures.end();
}

bool check() {
    for(auto structure : structures) { // set 탐색
        int x = structure.x, y = structure.y, st = structure.st;
        
        if(st==0) { // 기둥
            vector<node> info = {{x,y,1}, {x-1,y,1}, {x,y-1,0}};
            if(has(info[0]) || has(info[1]) || has(info[2]) || y==0) continue;
            return false;
        } else { // 보
            vector<node> info = {{x-1,y,1}, {x+1,y,1}, {x,y-1,0}, {x+1,y-1,0}};
            if((has(info[0])&&has(info[1])) || has(info[2]) || has(info[3])) continue;
            return false;
        }
    }
    
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    
    for(vector<int> build : build_frame) {
        node target = {build[0], build[1], build[2]};
        
        if(build[3]==0) { // 삭제
            structures.erase(target);
            if(!check()) structures.insert(target); // 조건을 만족하지 못하면 다시 추가
        } else { // 설치
            structures.insert(target);
            if(!check()) structures.erase(target); // 조건을 만족하지 못하면 다시 삭제
        }
    }
    
    for(auto ans : structures) {
        vector<int> re = {ans.x, ans.y, ans.st};
        answer.push_back(re);
    }
    
    return answer;
}

0개의 댓글