공부하자!/알고리즘
백준 21608 상어 초등학교 Swift - 구현
지우개원정대
2023. 6. 20. 23:14
주변에 좋아하는 학생이 많도록 자리를 배치하는 문제
문제 자체는 이해가 쉬웠다!
그대로 구현하는 게 시간이 걸릴 뿐...🤯
사실 며칠 전에 풀다가 만 코드가 있었는데,
다시 보니까 무슨 소린지 전혀 모르겠어서 처음부터 다시 짰다 ㅋㅋ
정확하게 뭘 짜야 하는지 주석부터 달고 시작했더니 가닥이 쉽게 잡히는 것 같다
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())