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

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

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

 

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

using namespace std;

enum {PILLAR, BEAM};

// 설치물 전체의 정합성 체크
bool check(const set<vector<int>> &s)
{
    for (const vector<int> &v : s)
    {
        int x = v[0];
        int y = v[1];
        int type = v[2];

        if (type == PILLAR)
        {
            /*
                현재 위치가 바닥이거나 왼쪽에 기둥이 있거나 
                위쪽에 보가 있거나 같은 위치에 보가 있어야 true
            */
            if ( !(y == 0 || s.count({x, y - 1, PILLAR })
                || s.count({ x - 1, y, BEAM }) || s.count({ x, y, BEAM })) )
            {
                return false;
            }
        }
        else 
        {
            /*
                왼쪽에 기둥이 있거나 왼,아래쪽에 기둥이 있거나 
                위아래에 보가 있어야 true
            */
            if ( !(s.count({x, y - 1, PILLAR}) || s.count({ x + 1, y - 1, PILLAR })
                || ( s.count({ x - 1, y, BEAM }) && s.count({ x + 1, y, BEAM }) ) ) )
            {
                return false;
            }
        }
    }
   
    return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {

    set<vector<int>> s;

    for (vector<int> &v : build_frame)
    {
        int x = v[0];
        int y = v[1];
        int type = v[2];
        int work = v[3];
        
        // 설치할 때
        if (work == 1)
        {
            s.insert({x, y, type });
            
            // 정합성이 맞지 않으면 다시 지우기
            if (!check(s))
            {
                s.erase({x, y, type});
            }
        }
        // 철거할 때
        else 
        {
            s.erase({ x, y, type });

            // 정합성이 맞지 않으면 다시 설치하기
            if (!check(s))
            {
                s.insert({ x, y, type });
            }
        }
    }

    /*
        set -> vector 옮겨주기
        set이 오름차순을 유지하기 때문에 정렬은 필요X
    */
    vector<vector<int>> answer;
    copy(s.begin(), s.end(), back_inserter(answer));

    return answer;
}

 

이 블로그를 참고한 풀이이다. 

사실 매 작업을 수행할 때마다 전체 설치물의 정합성을 체크하기 때문에

시간 복잡도상으로 베스트인 풀이는 아니지만, 나의 리얼타임 상으로는 매우 효율적이다...!ㅋㅋ

 

 

이 풀이의 포인트는 다음과 같다.

1. 주어진 그림을 벡터 friendly하게 옆으로 회전시켜 생각하자

2. 해봤다가... 아니면 원복하자

3. 답안을 {위치, 타입} 벡터로 반환하라는 건 힌트다

 

 

1. 주어진 그림을 벡터 friendly하게 옆으로 회전시켜 생각하자

인생 2막을 시작하는 죠르디

그림을 위처럼 회전시켜서 풀이하면 된다.

 

 

 

2. 해봤다가... 아니면 원복하자

3. 답안을 {위치, 타입} 벡터로 반환하라는 건 힌트다

 

이문제는 기둥을 설치할때, 보를 설치할 때, 기둥을 철거할 때, 보를 철거할 때 가능한 조건과

동작 수행 후 주변에 미치는 영향의 처리 경우의 수가 너무 많다. 

물론 불가능한 건 아니지만 시간이 급한 코테환경에서는 약간의 비효율을 감수하는게 낫다고 생각한다.

게다가 동작의 크기도 최대 1000이기 때문에, 최악의 경우에도 시간복잡도가 O(1000 * 1000) 수준이다.

그리고 답안도 {위치, 타입} 벡터 형태로 반환하라는 건 전체를 점검하라는 일종의 힌트가 아닐까...? 

 

따라서 그냥 동작 하나를 수행 한 뒤, 전체를 점검해도 괜찮다.

s.insert({x, y, type });

// 정합성이 맞지 않으면 다시 지우기
if (!check(s))
{
    s.erase({x, y, type});
}