프로그래머스[programmers] - 거리두기 확인하기(C++)[LV2]

문제 설명

개발자를 희망하는 조르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야 하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리 1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

예를 들어,

5개의 대기실을 본 조르디는 각 대기실에서 응시자들이 거리두기를 잘 지키고 있는지 알고 싶어 졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실 별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실 별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해주세요

 

제한사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

입출력 예

places

[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]

[1, 0, 1, 1, 1]

입출력 예 #1

첫 번째 대기실

No.	0	1	2	3	4
0	P	O	O	O	P
1	O	X	X	O	X
2	O	P	X	P	X
3	O	O	X	O	X
4	P	O	X	X	P

• 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실

No.	0	1	2	3	4
0	P	O	O	P	X
1	O	X	P	X	P
2	P	X	X	X	O
3	O	X	X	X	O
4	O	O	O	P	P

• (0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
• (1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
• (4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.

세 번째 대기실

No.	0	1	2	3	4
0	P	X	O	P	X
1	O	X	O	X	P
2	O	X	P	O	X
3	O	X	X	O	P
4	P	X	P	O	X

• 모든 응시자가 거리두기를 지키고 있습니다.

네 번째 대기실

No.	0	1	2	3	4
0	O	O	O	X	X
1	X	O	O	O	X
2	O	O	O	X	X
3	O	X	O	O	X
4	O	O	O	O	O

• 대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.

다섯 번째 대기실

No.	0	1	2	3	4
0	P	X	P	X	P
1	X	P	X	P	X
2	P	X	P	X	P
3	X	P	X	P	X
4	P	X	P	X	P

• 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

 

문제 해석

1. 맨해튼 거리는 A(r1, c1) B(r2, c2) 일 때 |r1-r2|+|c1-c2|이다.
   1. 맨해튼 거리가 1이면 조건을 따져볼 필요가 없다.
      1. 거리두기를 지키지 않음.
   2. 맨해튼 거리가 2보다 크다면 그때의 사람 2명은 거리두기를 지키고 있다.
   3. 맨해튼 거리가 2라면 조건을 따져봐야 함.
      1. 첫 번째는 서로 같은 열, 같은 행에 위치할 때이다.
         1. 만약 같은 열에 위치한다면 A와 B 사이 행에 파티션이 있으면 거리두기를 지키는 것이다.
         2. 만약 같은 행에 위치한다면 A와 B사이 열에 파티션이 있으면 거리두기를 지키는 것이다.
      2. 두 번째는 서로 다른 열, 다른 행일 때이다.
         1. 나의 해석은 서로 대각선의 위치에 있다면 그 나머지 위치를 X로 채워주면 된다고 생각해서 정사각형으로 오려서 P가 아닌 위치에 파티션의 개수를 계산하고 파티션이 2개면 거리두기를 지켰고, 2가 아니라면 거리두기를 지키지 않는다고 판단했다.
2. 만약 강의실에 사람이 없다면 검사해 볼 필요도 없이 거리두기를 지키고 있다고 할 수 있다.

구현

1. 5X5를 하나씩 저장할 vector <stirng> str을 생성함.
2. 사람의 좌표를 넣을 pair <int, int> p를 생성함.
3. X의 좌표를 넣을 map <pair <int, int>, int> X을 생성함.
   1. pair <int, int> 값은 X의 좌표고 나머지 value값은 의미 없는 값임.
   2. 왜 map을 쓸려고 생각했냐면, 파티션의 위치를 바로 반환해주고 싶어서..? -> 지금 생각해보면 굳이 map을 안 써도 됐을 거 같은데..
4. 파티션이 있어야 할 위치를 저장할 pair <int, int> Y를 생성함.
   1. 이것도 굳이 이렇게 안 하고 더 똑똑한 방법이 있을 거 같은데 바로 생각난 방법이 이거네..
5. str을 for문 돌려서 str [i][j]가 P면 P에다가 좌표를 넣어주고, X면 X에다가 좌표와 value를 넣어줌.
6. 만약 P.size()==0이면 강의실에 사람이 없다는 뜻이니 answer에다가 1을 넣어주고 전부다 초기화 후 continue를 함.
7. P의 좌표를 비교해서 맨해튼 거리를 검사함. 검사하는 방법은 위 문제 해석과 동일하게 했다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<int> solution(vector<vector<string>> places);
int main()
{
    vector<vector<string>> ary;
    vector<int> a;
    ary = {{"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"}, {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"}, {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"}, {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"}, {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}};
    a = solution(ary);
    for (int i = 0; i < a.size(); i++)
    {
        cout << a[i] << " ";
    }
}
vector<int> solution(vector<vector<string>> places)
{
    vector<int> answer;
    bool flag;
    vector<string> str;
    vector<pair<int, int>> p;
    pair<int, int> Y;
    map<pair<int, int>, int> X;
    for (int i = 0; i < places.size(); i++)
    {
        flag = true;
        for (int j = 0; j < places.size(); j++) //한줄씩 뽑음
        {
            str.push_back(places[i][j]);
        }
        //첫 줄 다 받음. 여기서 한꺼번에 해결하자.
        for (int x = 0; x < str.size(); x++) // 5*5 강의실을 넣고
        {
            for (int y = 0; y < str.size(); y++)
            {
                if (str[x][y] == 'P')
                {
                    p.push_back(make_pair(x, y));
                }
                else if (str[x][y] == 'X')
                {
                    X.insert(make_pair(make_pair(x, y), 0));
                }
            }
        }
        if (p.size() == 0) //사람이 없을 때
        {
            flag = true;
            answer.push_back(1);
            X.clear();
            p.resize(0);
            str.resize(0);
            continue;
        }
        for (int a = 0; a < p.size(); a++)
        {
            for (int b = a + 1; b < p.size(); b++)
            {
                if (abs(p[a].first - p[b].first) + abs(p[a].second - p[b].second) > 2) // 2가 넘으면 비교할 필요가 없음.
                {
                    continue;
                }
                else if (abs(p[a].first - p[b].first) + abs(p[a].second - p[b].second) == 1) // 1이면 파티션이 있을수가없음.
                {
                    flag = false; //거리 두기를 지키지 않음.
                }
                else if (abs(p[a].first - p[b].first) + abs(p[a].second - p[b].second) == 2) // 2면 사이에 파티션이 있어야함.
                {
                    if (p[a].first == p[b].first) //같은 열일때는 행 사이에 있어야함.
                    {
                        int idx = (p[a].second + p[b].second) / 2;
                        // p[a].second = idx;
                        Y = make_pair(p[a].first, idx);
                        // map에서 파티션의 열 좌표가 size여야함.
                        if (X.find(Y) == X.end()) //파티션의 위치는 p[a].first와 idx가 되야함. 찾지못한경우  X.end()를 반환
                        {
                            flag = false; //파티션이 없다면 false반환
                            break;
                        }
                    }
                    else if (p[a].second == p[b].second) //같은 행일때는 열 사이에 있어야함.
                    {
                        int idx = (p[a].first + p[b].first) / 2;
                        // p[a].first = idx;
                        Y = make_pair(idx, p[a].second);
                        if (X.find(Y) == X.end()) //없으면
                        {
                            flag = false;
                            break;
                        }
                    }
                    else
                    {
                        int cnt = 0;
                        int Min_row = min(p[a].first, p[b].first);
                        int Max_row = max(p[a].first, p[b].first);
                        int Min_col = min(p[a].second, p[b].second);
                        int Max_col = max(p[a].second, p[b].second);
                        for (int k = Min_row; k <= Max_row; k++)
                        {
                            for (int z = Min_col; z <= Max_col; z++)
                            {
                                if (str[k][z] == 'X')
                                {
                                    cnt++;
                                }
                            }
                        }
                        if (cnt != 2)
                            flag = false;
                        cnt = 0;
                    }
                }
            }
        }
        X.clear();
        p.resize(0);
        str.resize(0);
        if (flag == false)
            answer.push_back(0);
        else
            answer.push_back(1);
    }
    return answer;
}

 

---

느낀 점 : 다른 사람들의 코드를 보고 내걸 보니 너무 지저분한 것 같다..

debug 없이 짤려니까 굉장히 어려웠다. debug를 안 하는 습관을 들여야 할 텐데... 

그리고 map의 활용을 아직 잘 못하는 것 같다. 문법이 많이 헷갈렸다. 

map의 pair를 find 하고 싶으면 pair를 그대로 넣어줘야 해서 거기서 조금 헤맨 것 같다.

더 많은 자료구조를 연습해야 할 듯.,.!