[Swift] 프로그래머스_프렌즈4블록

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다. 블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다. 입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

 

예시

    m      n                                                           board                                                     answer

4	5	["CCBDE", "AAADE", "AAABF", "CCBBF"]	14
6	6	["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]	15

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

 

풀이

나는 solution 함수 내에 두 가지 함수를 더 구현하였다.

2차원 배열이 주어졌을 때 블록을 지우는 함수와 블록이 지워진 뒤 빈 공간을 채우기 위해 다시 배치하는 함수.

• 블록을 지우는 함수

func check(_ arr: [[String.Element]], _ m: Int, _ n: Int) -> [[String.Element]]{
        
        var delete: [[Int]] = []
        var newArr: [[String.Element]] = arr
        
        // m 높이, n 폭인데 마지막 칸의 오른쪽과 아래를 확인하면 범위를 벗어나므로
        for i in 0..<m-1 {
            for j in 0..<n-1 {
                // 빈 칸은 "X"로 할 예정이기 때문
                if newArr[i][j] != "X" {
                    let temp = newArr[i][j]
                    // 네 칸이 다 같은 경우
                    if newArr[i][j+1] == temp && newArr[i+1][j] == temp && newArr[i+1][j+1] == temp {
                        delete.append([i,j])
                        delete.append([i+1,j])
                        delete.append([i,j+1])
                        delete.append([i+1,j+1])
                        
                    } else {
                        continue
                    }
                }
            }
        }
        // delete에서 중복되는 것을 지워준 뒤 count 계산
        count += Set(delete).count
        // 지운 부분은 "X"로
        for i in delete {
            newArr[i[0]][i[1]] = "X"
        }
        if newArr == arr {
            checkSame = 1
        }
        return newArr
    }

 

 

반복문을  통해 이차원 배열을 돌면서 2x2의 지울 수 있는 블록을 찾으면 delete라는 변수에 추가한 뒤 반복문이 끝나고나서 "X"로 바꿔준다. 처음에 반복문 안에서 지울 블록을 찾으면 delete에 넣은 뒤에 바로 "X"로 바꿔줬더니 다음 반복문에서 "X"로 인해 제대로 찾지 못했다.

여기서 보이는 count는 solution 함수 내에서 선언된 변수이다. 위 함수가 solution 함수 내에 있으므로 전역 변수로 이용된다. 이때 delete에는 중복되는 것들이 있을 것이므로 Set을 이용해 중복을 제거한 뒤 개수를 count에 더해주었다.

 

• 빈 공간을 채우기 위해 재배열해주는 함수

func makeNewArr(_ arr: [[String.Element]], _ m: Int, _ n: Int) -> [[String.Element]] {
        
        var newArr: [[String.Element]] = arr
        var tempNum: Int = 0
        
        // 세로로 한 줄씩 확인. 이때 아래에서부터 확인해야 더 간단함.
        for i in 0..<n {
            for j in (1..<m).reversed() {
                if newArr[j][i] == "X" {
                    tempNum = j
                    while tempNum >= 0 {
                        if newArr[tempNum][i] != "X" {
                            newArr[j][i] = newArr[tempNum][i]
                            newArr[tempNum][i] = "X"
                            break
                        } else {
                            tempNum -= 1
                        }
                    }
                }
            }
        }
        return newArr
    }

한 번 블록이 지워지고 난 뒤에는 중간중간에 "X"로 되어있을 것이다. 따라서 반복문을 통해 위의 값을 내려줘야하는데 처음에는 해당 블록 아래가 "X"이면 내려주는 식으로 구현했지만 생각해보니 그러면 맨 위 블록과 그 아래 블록이 있고 그 아래가 빈 공간일 때, 맨 위 블록에서는 바로 아래 비어있지않으므로 continue되어 두 번째 블록만 아래로 내려가게 된다. 그래서 다시 구현했을 땐 아래에서 부터 확인하였더니 두 번 확인할 필요없이 구현할 수 있었다.

 

전체 코드

import Foundation

func solution(_ m:Int, _ n:Int, _ board:[String]) -> Int {

    var block: [[String.Element]] = []
    var count: Int = 0
    // while문을 끝내기 위해
    var checkSame: Int = 0
    // 2차원 배열로 만들어줌
    for i in board {
        block.append(Array(i))
    }
    // m, n 을 이용해 중첩 for문을 돌려서 4개를 만족하면 temp에 넣어주고 값을 O로 바꿔줌. 블록을 다시 배열하는 함수를 구현 후 다시 반복
    // 탐색해서 지우는 함수와 배열하는 함수 구현
    
    // 탐색하는 함수
    func check(_ arr: [[String.Element]], _ m: Int, _ n: Int) -> [[String.Element]]{
        
        var delete: [[Int]] = []
        var newArr: [[String.Element]] = arr
        
        // m 높이, n 폭인데 마지막 칸의 오른쪽과 아래를 확인하면 범위를 벗어나므로
        for i in 0..<m-1 {
            for j in 0..<n-1 {
                // 빈 칸은 "X"로 할 예정이기 때문
                if newArr[i][j] != "X" {
                    let temp = newArr[i][j]
                    // 네 칸이 다 같은 경우
                    if newArr[i][j+1] == temp && newArr[i+1][j] == temp && newArr[i+1][j+1] == temp {
                        delete.append([i,j])
                        delete.append([i+1,j])
                        delete.append([i,j+1])
                        delete.append([i+1,j+1])
                        
                    } else {
                        continue
                    }
                }
            }
        }
        // delete에서 중복되는 것을 지워준 뒤 count 계산
        count += Set(delete).count
        // 지운 부분은 "X"로
        for i in delete {
            newArr[i[0]][i[1]] = "X"
        }
        if newArr == arr {
            checkSame = 1
        }
        return newArr
    }
    // 새로 배열하는 함수
    func makeNewArr(_ arr: [[String.Element]], _ m: Int, _ n: Int) -> [[String.Element]] {
        
        var newArr: [[String.Element]] = arr
        var tempNum: Int = 0
        
        // 세로로 한 줄씩 확인. 이때 아래에서부터 확인해야 더 간단함.
        for i in 0..<n {
            for j in (1..<m).reversed() {
                if newArr[j][i] == "X" {
                    tempNum = j
                    while tempNum >= 0 {
                        if newArr[tempNum][i] != "X" {
                            newArr[j][i] = newArr[tempNum][i]
                            newArr[tempNum][i] = "X"
                            break
                        } else {
                            tempNum -= 1
                        }
                    }
                }
            }
        }
        return newArr
    }
    while checkSame != 1 {
        block = check(block, m, n)
        block = makeNewArr(block, m, n)
    }
    return count
}

가장 먼저 나는 주어진 배열을 2차원배열로 만들어주었다. 만들어진 함수들도 모두 2차원 배열을 받는다.

마지막 부분에 checkSame을 볼 수 있다. 두 함수를 이용하여 반복문을 통해 더 이상 지울 블록이 없을 경우엔 반복문을 탈출해야했다. check함수에서 나온 리턴 값이 처음에 들어갔던 배열과 차이가 없는 경우에 반복문을 탈출하도록 작성했다. 그래서 블록 지우는 함수에서 조건문을 통해 checkSame을 바꿔주도록 하였고 이를 이용해 solution함수의 반복문에서 탈출할 수 있게 하였다.

 

결론

솔직히 처음에 봤을 때 계속 봐도 모르겠었다. 그래서 내 수준에 맞지 않는 문제구나 하는 생각을 하며 다른 분들의 풀이를 보는데 봐도 모르겠어서 며칠간 다른 공부를 하며 냅뒀었다. 그러다 들어가서 확인하는데 갑자기 풀이가 떠오르고 생각보다 빠르게 구현을 했다. 다른 분들의 코드와 관련이 있는지는 확인해보진 않았지만 갑자기 머릿속에서 떠오른대로 풀어서 맞으니 뿌듯했다. 하지만 내가봐도 시간복잡도가 많이 높다. 주어진 입력 조건이 크지 않기에 일단 구현을 목표로 완성했는데 좀 더 확인해봐야 할 것 같다. 다른 분들의 코드도 시간복잡도가 나랑 큰 차이가 없긴 했다.