👨🏻‍💻iOS 공부/Swift_알고리즘 풀이

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

728x90
반응형

https://programmers.co.kr/learn/courses/30/lessons/81302?language=swift 

 

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

[["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]

programmers.co.kr

 

2021 카카오 채용연계형 인턴십 문제로 구현에 가까운 문제이다. 

 

문제를 잘 읽어보면 유의해야할 조건들을 구할 수 있다. 

핵심 조건은 맨해튼 거리가 2 이하인 경우 거리두기를 지키지 않고 있다라고 보는 것이다. 단, 경로 내에 "X"가 위치할 경우 거리두기를 지키고 있는 것이다라고 판단할 수 있다. 

 

즉 직선 거리와 대각선 위치에 있을 경우로 크게 두 가지 케이스를 고려해줘야 한다. 

 

// P를 기준을 보자 
// 직선 - 가로로 거리가 2인 경우
P O P
O O O

// 직선 - 세로로 거리가 2인 경우
P O O
O O O
P O O

// 대각선 - 거리가 2인 경우 
P O O
O P O 
O O O

 

물론 여기서 맨해튼 거리가 1인 경우는 "X"를 고려해주지 않아도 된다. 

왜냐하면 1인 경우는 어떻게 해도 구제가 안되기 때문이다... 

 

// P를 기준을 보자 
// 직선 - 가로로 거리가 2인 경우
P O P
O O O

// 사이에 X가 있다면 거리두기를 지킬 수 있다. 
P X P
O O O

// 하지만 거리가 1인 경우, X가 들어갈 자리조차 없다.
P P
O O

P O 
P O

그렇기 때문에 거리가 2인 케이스와 1인 케이스를 구분해서 작성해줘야 한다. 

 

구성한 함수들은 다음과 같다. 

 

1. 맨해튼 거리를 구하는 함수
2. P의 좌표를 구하는 함수
3. P와 P 좌표 내에 X가 존재하는지 판단하는 함수 

 

1번 함수 먼저 봐보자! 

// 맨해튼 거리
func dist(_ x: (Int,Int), _ y: (Int,Int)) -> Int {
    return abs(x.0 - y.0) + abs(x.1 - y.1)
}

무난하게 수식을 옮겨 작성해주면 된다. 

 

2번 함수로 바로 고고!

// P의 좌표를 구하는 함수
func checkP(_ arr: [[String]], _ row: Int, _ col: Int) -> Bool {
    return arr[row][col] == "P"
}

해당 인덱스의 값이 P인지 확인해주고, 함수 사용시에 해당 좌표들을 따로 저장해줄 것이다. 

 

그리고 대망의 마지막 3번 함수!

// P와 P 사이에 X가 존재하는지 확인
func checkX(_ arr: [[String]], _ x: (Int,Int), _ y: (Int,Int)) -> Bool {
    if x.0 == y.0 {
        for i in x.1+1..<y.1 {
            if arr[x.0][i] != "X" {
                return false
            }
        }
    } else if x.1 == y.1 {
        for i in x.0+1..<y.0 {
            if arr[i][x.1] != "X" {
                return false
            }
        }
    } else {
        if arr[x.0][y.1] != "X" || arr[y.0][x.1] != "X" {
            return false
        }
    }
    
    return true
}

우선은 맨 처음에 봤던 케이스대로 위에서부터 "가로선상에 놓인 경우", "세로선상에 놓인 경우", "대각에 놓인 경우"이다. 

 

가로와 세로의 케이스에서는 본인과 상대방을 모두 비포함하도록 하기 위해 시작점에서는 +1을 해주고 종료 구간 또한 포함하지 않도록 열림 구간으로 설정해두었다. 

 

자 이제 주어진 places를 돌면서 확인해보는 코드 전문을 보도록 하자!

import Foundation

func solution(_ places:[[String]]) -> [Int] {
    // 결과 저장
    var result = [Int]()
    
    for place in places {
        // P의 좌표를 담을 리스트
        var students = [(Int,Int)]()
        // 인덱스 접근을 위해 원소 단위로 나눠준다. 
        let p = place.map { $0.map { String($0) } }
        
        // P인 경우 좌표를 저장해준다. 
        for i in 0..<5 {
            for j in 0..<5 {
                if checkP(p,i,j) {
                    students.append((i,j))
                }
            }
        }
        
        // 거리두기를 지키는 경우 : 1
        // 거리두기를 지키지 못하는 경우 : 0
        var val = 1
        
        // students 배열이 비어있을 수 있기에 우선 확인
        if !students.isEmpty {
            // students의 모든 조합을 따져본다. 
            for i in 0..<students.count-1 {
                for j in i+1..<students.count {
                    // 하나라도 해당될 경우 해당 대기실을 거리두기를 지키지 않는 것이기에 break 해준다. 
                    // 맨해튼 거리가 2인 경우
                    if dist(students[i], students[j]) == 2 {
                        // 경로에 알맞게 X가 있는지 확인, 없다면 0 리턴
                        if !checkX(p, students[i], students[j]) {
                            val = 0
                            break
                        }
                    // 맨해튼 거리가 1인 경우 >> 무조건 0 리턴
                    } else if dist(students[i], students[j]) == 1 {
                        val = 0
                        break
                    }
                }
            }
        }
        // 결과 배열에 하나씩 담는다. 
        result.append(val)
    }    
    return result
}

// 맨해튼 거리 구하는 함수
func dist(_ x: (Int,Int), _ y: (Int,Int)) -> Int {
    return abs(x.0 - y.0) + abs(x.1 - y.1)
}

// P의 좌표를 구하는 함수
func checkP(_ arr: [[String]], _ row: Int, _ col: Int) -> Bool {
    return arr[row][col] == "P"
}

// P와 P사이의 X 유무를 구하는 함수
func checkX(_ arr: [[String]], _ x: (Int,Int), _ y: (Int,Int)) -> Bool {
    // 모두 거리가 2인 경우!
    // P들이 가로선상에 놓인 경우
    if x.0 == y.0 {
        for i in x.1+1..<y.1 {
            if arr[x.0][i] != "X" {
                return false
            }
        }
    // P들이 세로선상에 놓인 경우
    } else if x.1 == y.1 {
        for i in x.0+1..<y.0 {
            if arr[i][x.1] != "X" {
                return false
            }
        }
    // P들이 대각선상에 놓인 경우
    } else {
        if arr[x.0][y.1] != "X" || arr[y.0][x.1] != "X" {
            return false
        }
    }
    
    return true
}

 

1,2,3번 함수를 적절하게 조건에 맞게 사용해주면 어렵지 않게 풀이할 수 있는 문제! 

구현의 조건이나 예외 케이스가 엄청 까다로운 편은 아니지만! 

무작정 맨해튼 거리 2 이하로 묶어서 풀게되면, 1인 경우를 더 쉽게 고려할 수 있는 길을 놓치게 된다는 것을 유의하며 풀어야 했던 문제였다. 

728x90
반응형