[C++] 프로그래머스 - 기둥과 보 설치

2020 KAKAO BLIND RECRUITMENT (2020 카카오 블라인드 채용 문제)

기둥과 보를 세우는 문제입니다.

기둥 조건
1. 아래 기둥 위
2. 아래 왼쪽 보
3. 아래 오른쪽 보

보 조건
1. 아래 왼쪽 기둥
2. 아래 오른쪽 기둥
3. 왼쪽, 오른쪽 보 사이

위의 조건이 부합할때 기둥과 보를 세우고 기둥과 보를 제거할때 인접한 기둥과 보가
위의 조건에 위반되지 않는지 확인 한 후 제거하였습니다.

하드코딩으로 짜서 코드가 길게 나왔는데 다른 해설을 본 결과

위의 조건을 확인하는 함수를 만들고
삽입을 한 후에 전체가 조건을 만족하는지 확인 한 후에 만족하면 성공적으로 삽입이 된 경우이며,
만족하지 않으면 삽입을 할 수 없는 경우이므로 삽입한 것을 다시 제거해줍니다.

제거도 마찬가지로 제거를 한 후에 전체적으로 조건을 만족하는지 확인한 후에
만족하지 않는 경우 제거한 것을 다시 삽입해주는 방식으로 문제를 해결할 수 있습니다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

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

  return false;
}

void add(vector<vector<int>> &answer, vector<int> build_frame)
{
  vector<int> temp;
  temp.push_back(build_frame[0]);
  temp.push_back(build_frame[1]);
  temp.push_back(build_frame[2]);

  answer.push_back(temp);
}

bool remove(vector<vector<int>> &answer, vector<int> build_frame)
{
  bool check[5];
  memset(check, false, sizeof(check));
  for (int i = 0; i < answer.size(); ++i)
  {
    if (build_frame[2] == 0)
    {
      if (build_frame[0] == answer[i][0] && build_frame[1] == answer[i][1] - 1 && answer[i][2] == 0)
      {
        check[0] = true;
      }
      if (build_frame[0] == answer[i][0] + 1 && build_frame[1] == answer[i][1] - 1 && answer[i][2] == 1)
      {
        check[1] = true;
        check[2] = true;
      }
      if (build_frame[0] == answer[i][0] && build_frame[1] == answer[i][1] - 1 && answer[i][2] == 1)
      {
        check[3] = true;
        check[4] = true;
      }

      if (check[0] | check[1] | check[2] | check[3] | check[4])
      {
        for (int j = 0; j < answer.size(); ++j)
        {
          if (check[0] && (build_frame[0] == answer[j][0] + 1 || build_frame[0] == answer[j][0]) && (build_frame[1] == answer[j][1] - 1 && answer[j][2] == 1))
          {
            check[0] = false;
          }

          if (build_frame[0] == answer[j][0] + 1 && build_frame[1] == answer[j][1] && answer[j][2] == 0)
          {
            check[1] = false;
            check[2] = false;
          }
          if (check[1] && build_frame[0] == answer[j][0] + 2 && build_frame[1] == answer[j][1] - 1 && answer[j][2] == 1)
          {
            check[1] = false;
          }
          if (check[2] && build_frame[0] == answer[j][0] && build_frame[1] == answer[j][1] - 1 && answer[j][2] == 1)
          {
            check[2] = false;
          }
          if (build_frame[0] == answer[j][0] - 1 && build_frame[1] == answer[j][1] && answer[j][2] == 0)
          {
            check[3] = false;
            check[4] = false;
          }
          if (check[3] && build_frame[0] == answer[j][0] - 1 && build_frame[1] == answer[j][1] - 1 && answer[j][2] == 1)
          {
            check[3] = false;
          }
          if (check[4] && build_frame[0] == answer[j][0] + 1 && build_frame[1] == answer[j][1] - 1 && answer[j][2] == 1)
          {
            check[4] = false;
          }
        }
        if (check[0] | check[1] | check[2] | check[3] | check[4])
        {
          return false;
        }
      }
    }
    else if (build_frame[2] == 1)
    {
      if (build_frame[0] == answer[i][0] && build_frame[1] == answer[i][1] && answer[i][2] == 0)
      {
        check[0] = true;
      }
      if (build_frame[0] == answer[i][0] - 1 && build_frame[1] == answer[i][1] && answer[i][2] == 0)
      {
        check[1] = true;
      }
      if (build_frame[0] == answer[i][0] + 1 && build_frame[1] == answer[i][1] && answer[i][2] == 1)
      {
        check[2] = true;
      }
      if (build_frame[0] == answer[i][0] - 1 && build_frame[1] == answer[i][1] && answer[i][2] == 1)
      {
        check[3] = true;
      }

      if (check[0] | check[1] | check[2] | check[3])
      {
        for (int j = 0; j < answer.size(); ++j)
        {
          if (check[0] && ((build_frame[0] == answer[j][0] && build_frame[1] == answer[j][1] + 1 && answer[j][2] == 0) || (build_frame[0] == answer[j][0] + 1 && build_frame[1] == answer[j][1] && answer[j][2] == 1)))
          {
            check[0] = false;
          }
          if (check[1] && ((build_frame[0] == answer[j][0] - 1 && build_frame[1] == answer[j][1] + 1 && answer[j][2] == 0) || (build_frame[0] == answer[j][0] - 1 && build_frame[1] == answer[j][1] && answer[j][2] == 1)))
          {
            check[1] = false;
          }
          if (check[2] && ((build_frame[0] == answer[j][0] + 1 && build_frame[1] == answer[j][1] + 1 && answer[j][2] == 0) || (build_frame[0] == answer[j][0] && build_frame[1] == answer[j][1] + 1 && answer[j][2] == 0)))
          {
            check[2] = false;
          }
          if (check[3] && ((build_frame[0] == answer[j][0] - 1 && build_frame[1] == answer[j][1] + 1 && answer[j][2] == 0) || (build_frame[0] == answer[j][0] - 2 && build_frame[1] == answer[j][1] + 1 && answer[j][2] == 0)))
          {
            check[3] = false;
          }
        }
        if (check[0] | check[1] | check[2] | check[3])
        {
          return false;
        }
      }
    }
  }
  return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame)
{
  int check;
  vector<int> temp;
  vector<vector<int>> answer;

  for (int i = 0; i < build_frame.size(); ++i)
  {
    if (build_frame[i][3] == 1)
    {
      if (build_frame[i][2] == 0)
      {
        if (build_frame[i][1] == 0)
        {
          add(answer, build_frame[i]);
          continue;
        }
        else
        {
          for (int j = 0; j < answer.size(); ++j)
          {
            if (build_frame[i][0] == answer[j][0] && build_frame[i][1] == answer[j][1] + 1 && answer[j][2] == 0)
            {
              add(answer, build_frame[i]);
              break;
            }
            else if (build_frame[i][0] == answer[j][0] && build_frame[i][1] == answer[j][1] && answer[j][2] == 1)
            {
              add(answer, build_frame[i]);
              break;
            }
            else if (build_frame[i][0] == answer[j][0] + 1 && build_frame[i][1] == answer[j][1] && answer[j][2] == 1)
            {
              add(answer, build_frame[i]);
              break;
            }
          }
        }
      }
      else if (build_frame[i][2] == 1)
      {
        check = 0;
        for (int j = 0; j < answer.size(); ++j)
        {
          if (build_frame[i][0] == answer[j][0] && build_frame[i][1] == answer[j][1] + 1 && answer[j][2] == 0)
          {
            add(answer, build_frame[i]);
            break;
          }
          else if (build_frame[i][0] == answer[j][0] - 1 && build_frame[i][1] == answer[j][1] + 1 && answer[j][2] == 0)
          {
            add(answer, build_frame[i]);
            break;
          }
          else if (build_frame[i][0] == answer[j][0] - 1 && build_frame[i][1] == answer[j][1] && answer[j][2] == 1)
          {
            check += 1;
          }
          else if (build_frame[i][0] == answer[j][0] + 1 && build_frame[i][1] == answer[j][1] && answer[j][2] == 1)
          {
            check += 10;
          }
          if (check == 11)
          {
            add(answer, build_frame[i]);
            break;
          }
        }
      }
    }
    else if (build_frame[i][3] == 0)
    {
      for (int j = 0; j < answer.size(); ++j)
      {
        if (build_frame[i][0] == answer[j][0] && build_frame[i][1] == answer[j][1] && build_frame[i][2] == answer[j][2])
        {
          if (remove(answer, build_frame[i]))
          {
            answer.erase(answer.begin() + j);
            break;
          }
        }
      }
    }
  }

  sort(answer.begin(), answer.end(), compare);

  return answer;
}