백준 21608 상어 초등학교 Swift - 구현

주변에 좋아하는 학생이 많도록 자리를 배치하는 문제

 

문제 자체는 이해가 쉬웠다!

그대로 구현하는 게 시간이 걸릴 뿐...🤯

 

사실 며칠 전에 풀다가 만 코드가 있었는데,

다시 보니까 무슨 소린지 전혀 모르겠어서 처음부터 다시 짰다 ㅋㅋ

정확하게 뭘 짜야 하는지 주석부터 달고 시작했더니 가닥이 쉽게 잡히는 것 같다

 

let n = Int(readLine()!)!
var seats = Array(repeating: Array(repeating: 0, count: n), count: n) // 전체 좌석 만들기

우선 전체 좌석을 만들고 초기화해주었다

 

그리고 n * n 만큼 for문을 돌면서 한 줄씩 읽었다

한 명의 번호와 그 학생이 좋아하는 학생 번호들이 나열되기 때문에

한 줄을 읽을 때마다 실행해야할 것들이 많았음!

// 학생 번호와 좋아하는 학생 번호 받아오기
let numbers = readLine()!.split(separator: " ").map({Int($0)!})
 
// 학생들을 배치할 수 있는 칸 저장
var answer: [[Int]] = []
for i in 0...n - 1 {
    for j in 0...n - 1 {
        if seats[i][j] == 0 {
            answer.append([i, j])
        }
    }
}

배치가 가능한 칸을 초기화해줌

이 answer 배열을 이제 조건에 맞춰 하나씩 줄여갈 것이다

 

 

크게 세 가지 조건이 있었다

// 자리 배치하기
// 1. 비어있는 칸 중에 인접 칸에 좋아하는 학생이 많은 칸 찾기
answer = checkLike()
 
// 2. 남은 칸이 여러 개라면, 인접 칸에 비어있는 칸이 많은 칸 찾기
if answer.count > 1 {
    answer = checkEmpty()
}
 
// 3. 남은 칸이 여러 개라면, 행의 번호가 작은 칸, 또 여러 개라면 열의 번호가 작은 칸 찾기
if answer.count > 1 {
	answer = checkNum()
}
 
// 마지막 남은 좌석에 학생 배치!
seats[answer[0][0]][answer[0][1]] = student

이렇게 주석과 함수로 큰 틀을 잡아 놓고 시작을 해보았다

checkLike, checkEmpty, checkNum 은 answer 배열과 같은 [[Int]]를 return 할 것이라고 염두에 두고 시작

 

 

 

let dr = [0, 0, -1, 1]
let dc = [-1, 1, 0, 0]
 
// 1. 비어있는 칸 중에 인접 칸에 좋아하는 학생이 많은 칸 찾기
func checkLike(_ student: Int, likes: [Int], seatsLeft: [[Int]]) -> [[Int]] {
    var likeCountList: [Int] = Array(repeating: 0, count: seatsLeft.count) // 칸마다 인접 좋아하는 학생 수 세어 넣기 위한 초기화
    var maxLike = 0
    
    // 남은 좌석들 중 인접 네 칸에 좋아하는 학생이 있는 곳 세기
    for i in 0...seatsLeft.count - 1 {
        let seat = seatsLeft[i]
        var likeCount = 0 // 좋아하는 학생 수 세기 리셋
        let r = seat[0]
        let c = seat[1]
        for i in 0...3 { // 상하좌우 돌아가며 확인
            if r + dr[i] >= 0 && c + dc[i] >= 0 && r + dr[i] < n && c + dc[i] < n {
                if likes.contains(seats[r + dr[i]][c + dc[i]]) {
                    likeCount += 1
                }
            }
        }
        maxLike = max(maxLike, likeCount) // 가장 많은 칸을 위해 max값 업데이트
        likeCountList[i] = likeCount
    }
    
    var answer: [[Int]] = []
    for i in 0...likeCountList.count - 1 {
        if likeCountList[i] == maxLike {
            answer.append(seatsLeft[i]) // 가장 많이 인접한 칸을 모두 append
        }
    }
    
    return answer
}

우선 인접 상하좌우를 체크하기 위해 dr, dc를 만들었다

하나하나의 칸마다 인접한 좋아하는 학생 수를 적기 위해 likeCountList를 초기화했고,

근처에 좋아하는 학생이 가장 많은 곳은 몇 명이나 있을지를 확인하기 위해 maxLike를 정의했다

자리를 돌아가면서 하나씩 확인하고 가능한 자리를 answer에 append후 return 하는 것!!

 

 

// 2. 남은 칸이 여러 개라면, 인접 칸에 비어있는 칸이 많은 칸 찾기
func checkEmpty(_ student: Int, seatsLeft: [[Int]]) -> [[Int]] {
    var emptyCountList: [Int] = Array(repeating: 0, count: seatsLeft.count) // 칸마다 인접 빈 칸 세어 넣기 위한 초기화
    var maxEmpty = 0
    
    // 남은 좌석들 중 인접 네 칸에 빈 칸이 있는 곳 세기
    for i in 0...seatsLeft.count - 1 {
        let seat = seatsLeft[i]
        var emptyCount = 0 // 빈 칸 세기 리셋
        let r = seat[0]
        let c = seat[1]
        for i in 0...3 {
            if r + dr[i] >= 0 && c + dc[i] >= 0 && r + dr[i] < n && c + dc[i] < n {
                if seats[r + dr[i]][c + dc[i]] == 0 {
                    emptyCount += 1
                }
            }
        }
        maxEmpty = max(maxEmpty, emptyCount)
        emptyCountList[i] = emptyCount
    }
    
    var answer: [[Int]] = []
    for i in 0...emptyCountList.count - 1 {
        if emptyCountList[i] == maxEmpty {
            answer.append(seatsLeft[i])
        }
    }
    
    return answer
}

2번 함수도 위와 비슷한 방식으로 했다.

위와 겹치는 코드가 많아 잘하면 코드를 더 줄일 수도 있을 것 같은데,

더 헷갈릴 것 같아서 우선은 따로 만들었음!

 

이렇게 하나씩 하면 앉을만한 좌석이 하나씩 사라지고,

마지막으로 남는 좌석들은 행, 열 순서가 그대로 반영되어 저장되기 때문에

가장 앞에 있는 녀석으로 학생을 배치하면 된다

seats[answer[0][0]][answer[0][1]] = student

 

 

마지막으로 만족도 조사 함수는 1번 함수와 비슷하게 하나씩 돌면서

근처에 좋아하는 학생이 몇 명 있는지를 모두 체크하고 totalScore에 반영했다

// 만족도 조사
func review() -> Int {
    
    var totalScore = 0
    for i in 0...n - 1 {
        for j in 0...n - 1 {
            var likeCount = 0
            for k in 0...3 {
                if i + dr[k] >= 0 && j + dc[k] >= 0 && i + dr[k] < n && j + dc[k] < n {
                    let targetNum = seats[i + dr[k]][j + dc[k]]
                    if likeArr[seats[i][j]]!.contains(targetNum) { // 인접한 칸에 좋아하는 학생이 있는지 확인
                        likeCount += 1
                    }
                }
            }
            if likeCount != 0 {
                totalScore += Int(NSDecimalNumber(decimal: pow(10, likeCount - 1)))
            }
        }
    }
    return totalScore
}

여기서 pow 함수는 제곱을 구하는 함수인데, decimal이라서 Int로 바꿔주는 작업을 해야 함!

 

 

생각보다 쉬웠지만 그만큼 시간도 더 걸렸던 문제..!

구현 문제는 처음에 제대로 이해하고 큰 줄기를 잡아가며 풀어야 잘 풀리는 것 같다

 

---

전체 코드

import Foundation
 
let n = Int(readLine()!)!
var seats = Array(repeating: Array(repeating: 0, count: n), count: n) // 전체 좌석 만들기
var likeArr: [Int: [Int]] = [:] // 만족도 조사를 위헤 좋아하는 학생 리스트 저장해두기
 
let dr = [0, 0, -1, 1]
let dc = [-1, 1, 0, 0]
 
for _ in 0...n * n - 1 {
    // 학생 번호와 좋아하는 학생 번호 받아오기
    let numbers = readLine()!.split(separator: " ").map({Int($0)!})
    let student = Int(exactly: numbers[0])!
    let likes = numbers[1...4].map({Int(exactly: $0)!})
    likeArr[student] = likes
    
    // 학생들을 배치할 수 있는 칸 저장
    var answer: [[Int]] = []
    for i in 0...n - 1 {
        for j in 0...n - 1 {
            if seats[i][j] == 0 {
                answer.append([i, j])
            }
        }
    }
    
    // 자리 배치하기
    // 1. 비어있는 칸 중에 인접 칸에 좋아하는 학생이 많은 칸 찾기
    answer = checkLike(student, likes: likes, seatsLeft: answer)
    
    // 2. 남은 칸이 여러 개라면, 인접 칸에 비어있는 칸이 많은 칸 찾기
    if answer.count > 1 {
        answer = checkEmpty(student, seatsLeft: answer)
    }
    
    // 3. 남은 칸이 여러 개라면, 행의 번호가 작은 칸, 또 여러 개라면 열의 번호가 작은 칸 찾기
    // 자동으로 정렬되므로 따로 함수가 필요 없음
    // 배치할 수 있는 칸 중 맨 앞(작은 행, 작은 열)에 학생 배치하기
    seats[answer[0][0]][answer[0][1]] = student
}
 
// 1. 비어있는 칸 중에 인접 칸에 좋아하는 학생이 많은 칸 찾기
func checkLike(_ student: Int, likes: [Int], seatsLeft: [[Int]]) -> [[Int]] {
    var likeCountList: [Int] = Array(repeating: 0, count: seatsLeft.count) // 칸마다 인접 좋아하는 학생 수 세어 넣기 위한 초기화
    var maxLike = 0
    
    // 남은 좌석들 중 인접 네 칸에 좋아하는 학생이 있는 곳 세기
    for i in 0...seatsLeft.count - 1 {
        let seat = seatsLeft[i]
        var likeCount = 0 // 좋아하는 학생 수 세기 리셋
        let r = seat[0]
        let c = seat[1]
        for i in 0...3 { // 상하좌우 돌아가며 확인
            if r + dr[i] >= 0 && c + dc[i] >= 0 && r + dr[i] < n && c + dc[i] < n {
                if likes.contains(seats[r + dr[i]][c + dc[i]]) {
                    likeCount += 1
                }
            }
        }
        maxLike = max(maxLike, likeCount) // 가장 많은 칸을 위해 max값 업데이트
        likeCountList[i] = likeCount
    }
    
    var answer: [[Int]] = []
    for i in 0...likeCountList.count - 1 {
        if likeCountList[i] == maxLike {
            answer.append(seatsLeft[i]) // 가장 많이 인접한 칸을 모두 append
        }
    }
    
    return answer
}
 
// 2. 남은 칸이 여러 개라면, 인접 칸에 비어있는 칸이 많은 칸 찾기
func checkEmpty(_ student: Int, seatsLeft: [[Int]]) -> [[Int]] {
    var emptyCountList: [Int] = Array(repeating: 0, count: seatsLeft.count) // 칸마다 인접 빈 칸 세어 넣기 위한 초기화
    var maxEmpty = 0
    
    // 남은 좌석들 중 인접 네 칸에 빈 칸이 있는 곳 세기
    for i in 0...seatsLeft.count - 1 {
        let seat = seatsLeft[i]
        var emptyCount = 0 // 빈 칸 세기 리셋
        let r = seat[0]
        let c = seat[1]
        for i in 0...3 {
            if r + dr[i] >= 0 && c + dc[i] >= 0 && r + dr[i] < n && c + dc[i] < n {
                if seats[r + dr[i]][c + dc[i]] == 0 {
                    emptyCount += 1
                }
            }
        }
        maxEmpty = max(maxEmpty, emptyCount)
        emptyCountList[i] = emptyCount
    }
    
    var answer: [[Int]] = []
    for i in 0...emptyCountList.count - 1 {
        if emptyCountList[i] == maxEmpty {
            answer.append(seatsLeft[i])
        }
    }
    
    return answer
}
 
// 만족도 조사
func review() -> Int {
    
    var totalScore = 0
    for i in 0...n - 1 {
        for j in 0...n - 1 {
            var likeCount = 0
            for k in 0...3 {
                if i + dr[k] >= 0 && j + dc[k] >= 0 && i + dr[k] < n && j + dc[k] < n {
                    let targetNum = seats[i + dr[k]][j + dc[k]]
                    if likeArr[seats[i][j]]!.contains(targetNum) { // 인접한 칸에 좋아하는 학생이 있는지 확인
                        likeCount += 1
                    }
                }
            }
            if likeCount != 0 {
                totalScore += Int(NSDecimalNumber(decimal: pow(10, likeCount - 1)))
            }
        }
    }
    return totalScore
}
 
print(review())