[프로그래머스/Kotlin]거리두기 확인하기

문제 링크 - >https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

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

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을 담습니다.

------------------------------------------------------------풀이------------------------------------------------------------------
1. places[i]의 각 대기실 P의 x와 y좌표만 따로 추출한다. 
2. 추출된 p들 사이의 맨해튼거리가 2이하이면 주면에 파티션이 있는지 확인한다. 
 * 맨해튼 거리 | x-x1| + |y-y1|
 * 맨해튼 거리가 2 이하인 경우는 3가지 입니다. 

  - x좌표가 같을 때 |y-y1| <=2 인 경우 
   * y좌표로 place를 substring하여 파티션이 있는지 확인
 

 

 

  - y좌표가 같을 때 |x-x1| <=2 인 경우
   * x죽 좌표를 이동하면서 파티션이 있는지 확인한다.
 

 

 

 
- x좌표 y좌표 모두 다를 때 | x-x1| + |y-y1| <= 2 인 경우
   * 이 때는 두 p가 대각선으로 있는 경우이다.
   * 각 p의 위치를 확인한다. 
   * p가 왼쪽이라면 오른쪽 한칸만, 오른쪽이라면 왼쪽한칸만 확인해주면 된다.
   만약 P가 노란색 위치라면 맨해튼 거리는 2이상이므로 이런 경우는 없다.
   즉 x y가 다를 때 맨해튼 거리가 2이하인 경우는 왼쪽에 그림의 경우밖에 없다.

class Solution {
    fun solution(places: Array<Array<String>>): IntArray {
        var answer = ArrayList<Int>()
        var listX = ArrayList<Int>()
        var listY = ArrayList<Int>()

        for( i in places){
            for( j in 0..i.size-1){
                for( k in 0..i[j].length-1){
                    when(i[j][k]){
                        'P'->{ listX.add(j); listY.add(k) }
                    }
                }
            }
            if(checkDt(listX, listY, i)) answer.add(1) else answer.add(0)
            listX.clear(); listY.clear();
        }
        return answer.toIntArray()
    }

    fun checkDt( xList : ArrayList<Int>, yList : ArrayList<Int>, place : Array<String>) : Boolean{
        for( i in 0..xList.size-1){
            for( j in i+1..xList.size-1){
                val dt = abs(xList[i] - xList[j]) + abs( yList[i] - yList[j])
                if(dt <= 2){
                    if(xList[i] == xList[j]){ //x축 좌표가 같읗때
                        if(yList[i] > yList[j]){
                            if( !place[xList[i]].substring( yList[j], yList[i]).contains("X") ) return false
                        }
                        else{
                            if( !place[xList[i]].substring( yList[i], yList[j]).contains("X") ) return false
                        }
                    }
                    else if(yList[i] == yList[j]){ //y축 좌표가 같을 때
                        var s : String = ""
                        if( xList[i] > xList[j]){
                            for( k in xList[j]..xList[i]) s += place[k][yList[i]].toString()
                            if(!s.contains("X")) return false
                        }
                        else{
                            for( k in xList[i]..xList[j]) s += place[k][yList[i]].toString()
                            if(!s.contains("X")) return false
                        }
                    }
                    else{// x y축 좌표가 둘다 다를 때
                        if( yList[i]> yList[j]){
                            if( !(place[xList[i]][yList[i]-1] == 'X' && place[xList[j]][yList[j]+1] == 'X') ) return false
                        }
                        else{
                            if( !(place[xList[i]][yList[i]+1] == 'X' && place[xList[j]][yList[j]-1] == 'X') ) return false
                        }
                    }
                }
            }
        }
        return true
    }
}

풀이를 쓰다가 생각 났는데 x축이나 y축 좌표가 같을때 거리가 저거보다 길어질 수가 없지 않나..?
그럼 x축 좌표가 같을 때는 substring에 contains보다 그냥 어느 p가 더 왼쪽인지 확인해서 오른쪽만 확인하고 
y축 좌표가 같을 때는 어느 p가 더 위에 있는지 확인해서 아래쪽만 확인하면 되잖아..?
그래서 수정했다. 

import java.lang.Math.abs
class Solution {
    fun solution(places: Array<Array<String>>): IntArray {
        var answer = ArrayList<Int>()
        var listX = ArrayList<Int>()
        var listY = ArrayList<Int>()

        for( i in places){
            for( j in 0..i.size-1){
                for( k in 0..i[j].length-1){
                    when(i[j][k]){
                        'P'->{ listX.add(j); listY.add(k) }
                    }
                }
            }
            if(checkDt(listX, listY, i)) answer.add(1) else answer.add(0)
            listX.clear(); listY.clear();
        }
        return answer.toIntArray()
    }

    fun checkDt( xList : ArrayList<Int>, yList : ArrayList<Int>, place : Array<String>) : Boolean{
        for( i in 0..xList.size-1){
            for( j in i+1..xList.size-1){
                val dt = abs(xList[i] - xList[j]) + abs( yList[i] - yList[j])
                if(dt <= 2){
                    if(xList[i] == xList[j]){ //x축 좌표가 같읗때
                        if(yList[i] > yList[j]){ //수정 부분
                            if( place[xList[i]][yList[j]+1] != 'X' ) return false 
                        }
                        else{
                            if( place[xList[i]][yList[i]+1] != 'X' ) return false
                        }
                    }
                    else if(yList[i] == yList[j]){ //y축 좌표가 같을 때
                        if( xList[i] > xList[j]){ //수정 부분
                            if( place[xList[j]+1][yList[i]] != 'X' ) return false
                        }
                        else{
                            if( place[xList[i]+1][yList[i]] != 'X' ) return false
                        }
                    }
                    else{// x y축 좌표가 둘다 다를 때
                        if( yList[i]> yList[j]){
                            if( !(place[xList[i]][yList[i]-1] == 'X' && place[xList[j]][yList[j]+1] == 'X') ) return false
                        }
                        else{
                            if( !(place[xList[i]][yList[i]+1] == 'X' && place[xList[j]][yList[j]-1] == 'X') ) return false
                        }
                    }
                }
            }
        }
        return true
    }
}

------------------------------------------------------------결과------------------------------------------------------------------

수정 전 결과

수정 후 결과 

전체적으로 실행 시간이 줄었고 위에 보이진 않지만, 테스트 케이스 15번제외 모든 케이스가 실행시간이 10ms를 넘지않는다. 
30ms가 넘어간던 케이스도 7ms정도로 줄었다. 
역시 반복문이랑 contains가 영향이 엄청나게 크다.. 

 

 

다른분 풀이는 p가 확인되면 상하좌우를 모두 확인 해서 P가 있는지 확인하고 파티션을 확인하던데 이제 실행시켜보고 비교해봐야겠다.