프로그래머스 문제풀이

거리두기 확인하기

이 문제는 1년전에 회사 면접볼 때 어디 회사에서 코테로 주어진 문제였는데 그 때 당시에는 풀지 못했습니다..(시간제한은 1시간이였습니다.)

정답률 43프로... 어려운 문제였구만...하면서 지금의 나는 그 때보다 성장했으니 풀수있겠다는 자신감을 가지고 풀어보았습니다.

문제 내용

위에서 말하는 맨해튼 거리란 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다.

문제 풀이

저는 풀이를 일단 사람이 있는 좌표를 먼저 구하여 배열에 담고
만약 사람이 0명이거나 1명이면 성공.
그리고 반복문으로 사람의 좌표를 서로 비교하여 맨해튼 거리가 1이하면 실패, 2보다 크면 성공 만약에 거리가 2라면 파티션의 위치를 체크하여 성공 실패 여부를 판가름 하였습니다.

코드

function solution(places) {
    var answer = [];
    var personPlace = [];
    var count = 0;
    
    for(var i = 0; i < 5; i++) {
        personPlace = [];
        count = 0;
        
        for(var j = 0; j < 5; j++) {
            for(var k = 0; k < 5; k++) {
                if(places[i][j][k] == 'P') {
                    personPlace.push([j,k]);
                }
            }
        } //사람이 있는 위치 체크
        
        if(personPlace.length == 0 || personPlace.length == 1) {
            answer.push(1);
            continue;
        }//사람이 0명이거나 1명이면 무조건 성공
        
         for(var x = 0; x < personPlace.length - 1; x++) {
            for(var y = x + 1; y < personPlace.length; y++) {
                if (Math.abs(personPlace[x][0] - personPlace[y][0]) + 
                   Math.abs(personPlace[x][1] - personPlace[y][1]) == 1) {
                    count++;
                    break;
                } //거리가 1이면 무조건 실패
                
                if(Math.abs(personPlace[x][0] - personPlace[y][0]) + 
                   Math.abs(personPlace[x][1] - personPlace[y][1]) > 2) {
                    continue;
                } //거리가 2보다 크면 무조건 성공
                
                //여기서부터 거리가 2인 경우 조건
                if(personPlace[x][0] == personPlace[y][0]) {
                    var betweenValue = (personPlace[x][1] + personPlace[y][1]) / 2;
                    if(places[i][personPlace[x][0]][betweenValue] != 'X') {
                        count++;
                        break;
                    }
                } //같은 행에 있을시 조건
                
                if(personPlace[x][1] == personPlace[y][1]) {
                    var betweenValue = (personPlace[x][0] + personPlace[y][0]) / 2;
                    if(places[i][betweenValue][personPlace[x][1]] != 'X') {
                        count++;
                        break;
                    }
                } //같은 열에 있을시 조건
                
                if(Math.abs(personPlace[x][0] - personPlace[y][0]) == 1 && 
                   Math.abs(personPlace[x][1] - personPlace[y][1]) == 1 ) {
                    if(places[i][personPlace[x][0]][personPlace[y][1]] != 'X' ||
                        places[i][personPlace[y][0]][personPlace[x][1]] != 'X') {
                        count++;
                        break;
                    }
                     
                } //크로스 됐을때 조건
                
            }
             if(count > 0) {
                 answer.push(0);
                 break;
             } //실패시 카운트 업해서 카운트가 1이상이면 실패
        }
        if(count == 0) {
            answer.push(1);
        } // 최종까지 카운트가 0이라면 성공
    }
    
    return answer;
}

이렇게 풀이해보았는데요. 사실 문제를 푸는데 1시간 20분 정도가 걸렸습니다..(그 때로 다시 돌아가서 풀었어도 못풀었다는 슬픈 결말...) 문제를 풀면서 느낀점은 문제를 접근하는데에 시간이 너무 오래걸린다는 점과 이런 관련한 알고리즘 공부를 하면 도움이 될것같다 라는 생각이 많이 들었던 문제 풀이였던것 같습니다.