2021 카카오 채용연계형 인턴십 (거리두기 확인하기)

문제를 어디서 많이 봤다고 생각했는데 작년에 실제로 테스트 봤던 문제였다. 당시에는 Python으로 문제를 풀었었다.

당시 작성했던 코드가 있는데 지금 보면 어떻게 풀었는지 알수가 없다. (뭔가 알고리즘 없이 맨해튼 거리로만 푼거 같은데 도저히 이해 불가능) 

 

def solution(places):
    answer = [0,0,0,0,0]

    for place_num,place in enumerate(places):
        person_location = []
        flag =True
        for i,row in enumerate(place):
            for j in range(len(row)):
                if row[j]=="P":
                    person_location.append((i,j))
        
        for i in range(len(person_location)):
            for j in range(i+1,len(person_location)):
                if abs(person_location[i][0] - person_location[j][0]) + abs(person_location[i][1] - person_location[j][1]) <2:
                    flag=False
                if abs(person_location[i][0] - person_location[j][0]) + abs(person_location[i][1] - person_location[j][1]) == 2:
                    if person_location[i][0] == person_location[j][0]:
                        if place[person_location[i][0]][int((person_location[i][1]+person_location[j][1])/2)] =="O":
                            flag=False
                    if person_location[i][1] == person_location[j][1]:
                        if place[int((person_location[i][0]+person_location[j][0])/2)][person_location[i][1]] =="O":
                            flag=False
                    if place[person_location[i][0]][person_location[j][1]] =="O" or place[person_location[j][0]][person_location[i][1]] =="O":
                        flag= False
        if flag:
            answer[place_num] =1

    return answer

if __name__ =="__main__":
    s= [
        ["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], 
        ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], 
        ["PXOPX", "OXOXP", "OXPXX", "OXXXP", "POOXX"], 
        ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], 
        ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]
        ]
    print(solution(s))

 

결국 답은 맞긴했는데 아마 이 문제만 2시간 넘게 풀었던거 같다....

 

P = 앉음

X = 파티션

O = 빈자리

 

C++ 로 풀어보자!

핵심은 빈자리를 기준으로 주변(상,하,좌,우)에 앉은 사람이 1명 이상인 경우 두 사람의 맨해튼 거리는 2가 되는 것을 이용하였다. (BFS는 아니지만 이전에 Python으로 직접 거리를 계산하지는 않았다.)

 

빈자리의 좌표를 배열에 넣어주고 순회하면서 각각 상,하,좌,우를 확인한다.

이 방법을 적용하면 테스트코드는 통과한다. 하지만 반례가 있다. 빈 자리만 기준으로 하였기 때문에 빈자리가 없고 사람이 연속적으로 앉았을 경우를 확인하지 않았다. 

 

이번엔 사람을 기준으로 상,하,좌,후를 확인해본다. 사람을 기준으로 주변에 앉은 사람이 없어야 조건을 만족한다.

따라서 정답은 빈 자리(O) 기준과, 앉음(P)의 기준을 동시에 만족해야한다. 

 

#include <string>
#include <vector>

using namespace std;

int x[4] = { 0,1,0,-1 };
int y[4] = { 1,0,-1,0 };

vector<int> solution(vector<vector<string>> places) {
  vector<int> result;

	for(int i = 0; i < places.size(); i++)
	{
		vector<vector<char>> p(5,vector<char>(5));
		vector<pair<int, int>> empty;
		vector<pair<int, int>> pSit;

		for(int j=0; j< places[i].size();j++)
		{
			for(int k = 0; k < places[i][j].length(); k++)
			{
				p[j][k] = places[i][j][k];
				if(p[j][k] == 'O')
				{
					empty.push_back({ j,k });
				}
				if(p[j][k] == 'P')
				{
					pSit.push_back({ j,k });
				}
			}
		}

		bool emptyPossible = true;
		bool sitPossible = true;

		for(int j = 0; j < empty.size(); j++)
		{
			int cnt = 0;
			for(int k = 0; k < 4; k++)
			{
				int nx = empty[j].first + x[k];
				int ny = empty[j].second + y[k];
				if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && p[nx][ny] == 'P')
				{
					cnt++;				
				}
			}
			if(cnt > 1)
			{
				emptyPossible = false;
				break;
			}
		}

		for(int j = 0; j < pSit.size(); j++)
		{
			int cnt = 0;
			for(int k = 0; k < 4; k++)
			{
				int nx = pSit[j].first + x[k];
				int ny = pSit[j].second + y[k];
				if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && p[nx][ny] == 'P')
				{
					cnt++;
				}
			}
			if(cnt > 0)
			{
				sitPossible = false;
				break;
			}
		}


		if((emptyPossible && sitPossible) ==false)
		{
			result.push_back(0);
		}
		else
		{
			result.push_back(1);
		}
	}
    return result;
}

문제를 조금더 생각해보면 P를 기준으로 주변이 X인지 O인지에 따라 X일경우 넘어가고, O일경우 O주변에 출발한 P를 제외하고 P가 존재하는지 확인하면 될것 같다.

XXXXX

XXXPX

XXOOX

XXPOX

XXXPX