![[프로그래머스] 프렌즈4블록](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FCeYmf%2Fbtq4NKrVior%2FBJBMkMxFFqKQzKMzg6vlY1%2Fimg.gif)
programmers.co.kr/learn/courses/30/lessons/17679?language=swift
코딩테스트 연습 - [1차] 프렌즈4블록
프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙
programmers.co.kr
딱 봤을 때, 2X2 애니팡 같은 느낌이다..!
2x2블록의 구성 요소들이 모두 같다면 터지고, 위에 원소들이 내려오는 형태이다.
여기서 보면 라이언으로 이루어져 있는 블록 2개, 콘 블록 1개가 지워지게 된다.
중간 블록들이 지워지게 되면서 위에 위치한 블록들은 자연스레 내려와줘야 한다.
여기서 한 번 더 검사를 해서 더 터트릴 수 있는 블록이 있는지 확인한다.
한 블록 더 제거가 가능하니 없애주면
위와 같은 결과물을 얻을 수 있다.
생각을 해보면 프로세스는 간단해보인다.
1. 2x2 창으로 모든 블록들을 옮겨가며 확인해준다.
2. 구성요소들이 모두 같다면 제거
3. 블록들 재정비 (위치 이동)
4. 1,2,3번 반복
5. 더 이상 수행할 수 있는게 없다면 반환하고 종료
재귀를 사용해야 할 것 같은 느낌적인 느낌... 그냥 repeat, while문으로도 간단하게 해결할 수 있을 것 같아 반복문을 이용했다.
먼저 1번에 해당하는 블록 검사를 먼저 구현해보자.
func findBox(_ n: Int, _ board: [[String]]) -> [[Int]] {
// 지울 블록의 Index를 저장하기 위함
var duplicated = [[Int]]()
// 행
for i in 0..<board.count-1 {
// 열
for j in 0..<n-1 {
// 계속 적어주기 귀찮으니 할당
let v = board[i][j]
// 기준이 되는 원소 v가 "*" 가 아니고 바로 옆 원소와 동일할 때 다음 단계로 이동
if v != "*" && v == board[i][j+1] {
let v2 = board[i+1][j]
// 그 다음 단계 : 바로 아래줄의 2개를 확인 > 똑같다면 지워줘야 할 블록 index list에 append
if v == v2 && v == board[i+1][j+1] {
if !duplicated.contains([i,j]) {
duplicated.append([i,j])
}
if !duplicated.contains([i,j+1]) {
duplicated.append([i,j+1])
}
if !duplicated.contains([i+1,j]) {
duplicated.append([i+1,j])
}
if !duplicated.contains([i+1,j+1]) {
duplicated.append([i+1,j+1])
}
} // 위 조건 안맞는 것들은 그냥 패스!
}
}
}
return duplicated
}2X2 창으로 슬라이딩한다고 생각하면 이해하기 편할 것이다. (약간 CNN 같은 느낌..?)
노란 박스 안의 * 가 board[i][j] 즉, 기준이 되는 값이다.
노란 박스 안의 값들이 모두 같다면 중복리스트(duplicated)에 저장해두고, 배열을 모두 다 돌았다면 이를 반환해주면 된다.
이제 duplicated를 가지고 원배열의 값들을 바꾸고, 바뀐 값들에 영향을 받은 블록들을 옮겨줘야 한다!
func removeAndMoveBox(_ m: Int, _ board: inout [[String]], _ dup: [[Int]]) {
// remove
for d in dup {
board[d[0]][d[1]] = "*"
}
// 반복문 종료를 위한 지표
var signal = true
repeat {
// 더 이상 배열이 바뀌지 않으면 종료되도록!
var boardcopy = board
// 행
for i in 0..<board.count {
// 열
for j in 0..<m-1 {
// 세로를 기준으로 봐야한다.
// A * * A라면 중간 값들을 모두 지나치고 * * A A가 되어야 한다.
// 그렇기에 다음 값을 기준으로 판단하고 값들을 변경해준다.
if board[j+1][i] == "*" {
board[j+1][i] = board[j][i]
board[j][i] = "*"
}
}
}
// 카피와 원본이 같아지는 순간이 바로 더 이상 옮길 블록이 없다는 것이다.
signal = board != boardcopy
} while signal
}먼저 얻어둔 Index 값들로 원 배열에서 해당하는 값을 지워준다!
("*"도 되고, 빈 값도 되고 구분만 할 수 있으면 된다!)
그리고 반복문을 돌게 되는데, n+1번째 실행 결과 배열과 n번째 실행 결과 배열이 같아지면 종료되게 되어있다.
실행을 했는데도 배열이 같다..? 더 이상 옮길게 없다는 것이다! 곧 바로 종료!
핵심이 되는 부분들은 모두 구현했으니 이제 본게임으로 가보자!
func solution(_ m:Int, _ n:Int, _ board:[String]) -> Int {
// indexing 가능하도록 바꿔준다.
var board = board.map {$0.map {String($0)}}
// 아까 본 지표랑 같은 목적
var signal = true
repeat {
let boardcopy = board
let duplicated = findBox(n,board)
removeAndMoveBox(m, &board, duplicated)
signal = boardcopy != board
} while signal
return board.map {$0.filter{ $0 == "*"}.count}.reduce(0,+)
}여기서 부터 큰 어려움은 없다.
동일하게 n+1번째 실행 결과 배열과 n번째 실행 결과 배열이 같아지면 종료되게 되어있다.
그리고 마지막으로 반환되는 배열을 기준으로 "*"가 몇 개인지 세어 반환해주면 정답이 된다!
[프로세스]
* 위 참고
func solution(_ m:Int, _ n:Int, _ board:[String]) -> Int {
// indexing 가능하도록 바꿔준다.
var board = board.map {$0.map {String($0)}}
// 아까 본 지표랑 같은 목적
var signal = true
repeat {
let boardcopy = board
let duplicated = findBox(n,board)
removeAndMoveBox(m, &board, duplicated)
signal = boardcopy != board
} while signal
return board.map {$0.filter{ $0 == "*"}.count}.reduce(0,+)
}
func findBox(_ n: Int, _ board: [[String]]) -> [[Int]] {
// 지울 블록의 Index를 저장하기 위함
var duplicated = [[Int]]()
// 행
for i in 0..<board.count-1 {
// 열
for j in 0..<n-1 {
// 계속 적어주기 귀찮으니 할당
let v = board[i][j]
// 기준이 되는 원소 v가 "*" 가 아니고 바로 옆 원소와 동일할 때 다음 단계로 이동
if v != "*" && v == board[i][j+1] {
let v2 = board[i+1][j]
// 그 다음 단계 : 바로 아래줄의 2개를 확인 > 똑같다면 지워줘야 할 블록 index list에 append
if v == v2 && v == board[i+1][j+1] {
if !duplicated.contains([i,j]) {
duplicated.append([i,j])
}
if !duplicated.contains([i,j+1]) {
duplicated.append([i,j+1])
}
if !duplicated.contains([i+1,j]) {
duplicated.append([i+1,j])
}
if !duplicated.contains([i+1,j+1]) {
duplicated.append([i+1,j+1])
}
} // 위 조건 안맞는 것들은 그냥 패스!
}
}
}
return duplicated
}
func removeAndMoveBox(_ m: Int, _ board: inout [[String]], _ dup: [[Int]]) {
// remove
for d in dup {
board[d[0]][d[1]] = "*"
}
// 반복문 종료를 위한 지표
var signal = true
repeat {
// 더 이상 배열이 바뀌지 않으면 종료되도록!
var boardcopy = board
// 행
for i in 0..<board.count {
// 열
for j in 0..<m-1 {
// 세로를 기준으로 봐야한다.
// A * * A라면 중간 값들을 모두 지나치고 * * A A가 되어야 한다.
// 그렇기에 다음 값을 기준으로 판단하고 값들을 변경해준다.
if board[j+1][i] == "*" {
board[j+1][i] = board[j][i]
board[j][i] = "*"
}
}
}
// 카피와 원본이 같아지는 순간이 바로 더 이상 옮길 블록이 없다는 것이다.
signal = board != boardcopy
} while signal
}구현 문제.
머리로는 이해가 되었는데, 처음에 2x2로 어떻게 검사할지에 대한 아이디어를 마련하는데 어려움이 있었다.
통으로 보지 않고 잘라서 보는 방법으로 해결을 했고, 문제를 쪼개서 보는 것에 대한 중요성을 알 수 있었다..?
아무튼 여러 시각으로 문제를 바라보는 것이 중요한 것 같다. 무조건 한 가지 방법, 정답만이 있는 것은 아니기에..!