https://programmers.co.kr/learn/courses/30/lessons/81302?language=swift
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인 경우를 더 쉽게 고려할 수 있는 길을 놓치게 된다는 것을 유의하며 풀어야 했던 문제였다.