[프로그래머스] (Swift) Kakao - [1차] 프렌즈4블록 (Lv.2)

🟠 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/17679

프로그래머스

 

🟠 나의 풀이

1. 입력되는 board를 2차원 배열로 바꿔주기
2. 4개개로 모여있는 좌표를 탐색, removePoint (지우는좌표) 집합 (set)에 넣어주기
3. removePoint에 값들이 들어있다면, 해당 좌표를 "-"로 바꾸어 삭제처리 & cnt 지우는 블록 갯수 더해주기
4. 삭제된 부분 위에있는 블록들 내려주기

4개의 블록만 터뜨리는 것이므로, 탐색 알고리즘을 따로 쓰지 않았다. 그냥 구현으로 가능할 것 같아서! 그림을 그려보니, 지우는 좌표는 다음과 같았다.

첫번째 처럼 A가 여섯개가 있더라도, 4개씩 탐색 후, 중복되는 좌표들을 처리해주면 될 것같았다. 그래서 '지우는 좌표들'을 Set으로 구성하여 코드르 작성했다.

그리고 블록을 내려주는 로직은 아래와 같이 생각했다. 

아 그리고, 노란색 형광팬으로 칠한 부분만 봐주면서 블록을 처리했다. (i+1이나 j+1이 되는 부분은 굳이 for문 범위 내에 안넣어줘도 되기 때문이다!

첫번째로 짠 코드는 아래와 같다. 근데 test case 5번과 10번에서 실패가 떴다. 시간초과가 아니고 실패인 이상, 어떤 case에서는 내 로직이 잘못됐구나를 파악했다.

실패코드

//
//  main.swift
//  Algorithm
//
//  Created by LeeJiSoo on 2022/09/03.
//

import Foundation

let m = 4
let n = 5
let board = ["CCBDE", "AAADE", "AAABF", "CCBBF"]
// 결과값 : 14

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

    // board를 2차원 배열로 바꿔주기
    var newBoard = splitBoard(board)

    // 지우는 좌표를 기록하기 위한 set 설정 & return 값 설정
    var removePoint = Set<[Int]>()
    var cnt = 0

    // 프렌즈 4블록이 없어질때까지 돌려야하니까, while 문으로 removePoint 조건 검사
    // 원래 while !removePoint.isEmpty 을 조건으로 주었는데, removePoint는 매번 초기화해주니까 이 조건은 안되는구나를 깨닳음
    while true {
        // 4블록 위치 찾아서 removePoint에 넣어주기
        for i in 0..<m-1 {
            for j in 0..<n-1 {
                let point = newBoard[i][j]
                // 만약 point 가 - 라면, 이미 제거된 위치이므로 continue
                if point == "-" {
                    continue
                }
                // 사방을 보고 다 point 와 같다면 removePoint에 해당 좌표 추가
                if newBoard[i][j+1] == point, newBoard[i+1][j] == point, newBoard[i+1][j+1] == point {
                    removePoint.insert([i, j])
                    removePoint.insert([i, j+1])
                    removePoint.insert([i+1, j])
                    removePoint.insert([i+1, j+1])
                }
            }
        }

        // removiPoint가 있으면 cnt 더해주고 블록 지우고, 없으면 끝 cnt 출력
        if !removePoint.isEmpty {
            cnt += removePoint.count
            for point in removePoint {
                newBoard[point[0]][point[1]] = "-"
            }
            removePoint = Set<[Int]>()
        } else {
            break
        }

        // 지금 블록 없는 곳이 "-"인데, 블록을 차례대로 밑으로 내려줘야함
        for i in 0..<m-1 {
            for j in 0..<n {
                let block = newBoard[i][j]
                let under = newBoard[i+1][j]
                if under == "-" {
                    newBoard[i][j] = "-"
                    newBoard[i+1][j] = block
                } else {
                    continue
                }
            }
        }
    }
    return cnt
}


func splitBoard(_ board: [String]) -> [[String]] {
    var newBoard = [[String]]()
    for b in board  {
        let arr = b.map { String($0) }
        newBoard.append(arr)
    }
    return newBoard
}

print(solution(m, n, board))

인터넷을 찾아보니까 많은 사람들이 다양한 원인으로 5번과 10번을 통과하지 못하고 있었다

1. 공백에 대한 처리를 해주지 않았기 때문에 통과하지 못했다는 분
https://lsh424.tistory.com/85

나는,, 공백에 대한 처리를 완전히 해주었고, 이 블로그에서 알려주는 반례를 대입해봐도 정상적으로 작동했다. 나는 이 원인은 아닌 것 같다.

2. 반례 통과하는지 살펴보기 + 배열을 재배치(블록을 내릴때) 할 때 잘못 했다고 하시는 분
(반례참고)https://dev-note-97.tistory.com/105
(블록내릴 때 오류라고 하시는 분, 코드 참고) https://velog.io/@syi07030/Swift-%EA%B3%B5%EB%B6%80-Programmers-1%EC%B0%A8-%ED%94%84%EB%A0%8C%EC%A6%884%EB%B8%94%EB%A1%9D-level2-2018-KAKAO-BLIND-RECRUITMENT

이 블로그에서 제시한 반례를 통과하지 못하는 오류를 발견했다. 

// 반례
let m = 5
let n = 6
let board = ["AAAAAA","BBAATB","BBAATB","JJJTAA","JJJTAA"]
// 결과값 : 24

대부분 반례를 통과하지 못하는 이유는, 블록을 내릴때 잘못된 로직으로 발생한 것 같았다. 그래서 블록을 내려주는 방식을 수정해보기로 한다.

도저히 무슨 원인인지 몰라서, 다른 코드를 찾아봤다. removePoint를 삭제하고, 블록을 밑으로 내려주는 과정에서 대부분의 사람들은 '거꾸로' 진행했다. 즉, 나는 위에서부터 차례대로 for문을 돌려서, 밑에 "-"면, 위랑 아래랑 바꿔라~ 이런 순서로 진행했다. 하지만 이렇게 하게 되면 아래와 같은 문제가 발생한다.

이런 문제가 발생하기 때문에 답이 24가 나와야하는 반례에서 20으로 나온것이고, AA,TB가 제대로 내려오지 않아서 삭제되지 않은 4개가 count 되지 않았떤 것이다.

그래서 사람들이 for문을 돌릴때, 밑부분 부터 돌렸구나,, 그래서 참고한 코드는 아래와 같다.

// 5번 10번 실패 코드 
// 블록 내리는 부분의 코드
//        for i in 0..<m-1 {
//            for j in 0..<n {
//                let block = newBoard[i][j]
//                let under = newBoard[i+1][j]
//                if block != "-", under == "-" {
//                    newBoard[i+1][j] = block
//                    newBoard[i][j] = "-"
//                } else {
//                    continue
//                }
//            }
//        }


// 이렇게 바꿔야한다.
for j in stride(from: 0, to: n, by: 1){ //열
    var first = 0 //블록이 내려와야할 행 위치
    if newBoard[m-1][j] == "-" {
        first = m-1
    }

    for i in stride(from: m-2, through: 0, by: -1){ //행
        if newBoard[i][j] == "-" {
            if i > first {
                first = i
            }
        } else if newBoard[i+1][j] == "-"{
            newBoard[first][j] = newBoard[i][j]
            newBoard[i][j] = "-"
            first -= 1
        }
    }
}

 

도대체 시험볼때 이런 반례를 어떻게 생각하냔 말이다 ㅠㅠㅠ 아직 실력이 많이 부족한가보다. 어디서 실패가 떳는지 전혀 감을 잡지 못해서 여러 인터넷을 참고해봤다. 다들 왜 천재같지?

 

즉, 가장 중요한 것은, 블록을 아래로 내리는 과정 -> 순서대로 탐색하는게 아니라, 밑에서부터 탐색해서 차근차근 위로 올라가면서 내려주는게 올바른 방법이다!!

 

🟠 정답코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Programmers/kakao_%ED%94%84%EB%A0%8C%EC%A6%884%EB%B8%94%EB%A1%9D/main.swift

GitHub - deslog/Algorithm: ✨ 백준, 프로그래머스 Swift 문제풀이 ✨

 

import Foundation

//let m = 4
//let n = 5
//let board = ["CCBDE", "AAADE", "AAABF", "CCBBF"]
// 결과값 : 14

// 다른 test case
//let m = 8
//let n = 2
//let board = ["CC", "BB", "AA", "BB", "BB", "AA", "BB", "CC"]
// 결과값 : 16

// 반례
let m = 5
let n = 6
let board = ["AAAAAA","BBAATB","BBAATB","JJJTAA","JJJTAA"]
// 결과값 : 24

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

    // board를 2차원 배열로 바꿔주기
    var newBoard = splitBoard(board)

    // 지우는 좌표를 기록하기 위한 set 설정 & return 값 설정
    var removePoint = Set<[Int]>()
    var cnt = 0

    // 프렌즈 4블록이 없어질때까지 돌려야하니까, while 문으로 removePoint 조건 검사
    // 원래 while !removePoint.isEmpty 을 조건으로 주었는데, removePoint는 매번 초기화해주니까 이 조건은 안되는구나를 깨닳음
    while true {
        // 4블록 위치 찾아서 removePoint에 넣어주기
        for i in 0..<m-1 {
            for j in 0..<n-1 {
                let point = newBoard[i][j]
                // 만약 point 가 - 라면, 이미 제거된 위치이므로 continue
                if point == "-" {
                    continue
                }
                // 사방을 보고 다 point 와 같다면 removePoint에 해당 좌표 추가
                if newBoard[i][j+1] == point, newBoard[i+1][j] == point, newBoard[i+1][j+1] == point {
                    removePoint.insert([i, j])
                    removePoint.insert([i, j+1])
                    removePoint.insert([i+1, j])
                    removePoint.insert([i+1, j+1])
                }
            }
        }

        // removiPoint가 있으면 cnt 더해주고 블록 지우고, 없으면 끝 cnt 출력
        if !removePoint.isEmpty {
            cnt += removePoint.count
            for point in removePoint {
                newBoard[point[0]][point[1]] = "-"
            }
            removePoint = Set<[Int]>()
        } else {
            break
        }

        // 지금 블록 없는 곳이 "-"인데, 블록을 차례대로 밑으로 내려줘야함
        // 해당 코드는 블록을 제대로 밑으로 못내려주는 문제가 있어서 아래 코드로 수정!
        //        for i in 0..<m-1 {
        //            for j in 0..<n {
        //                let block = newBoard[i][j]
        //                let under = newBoard[i+1][j]
        //                if block != "-", under == "-" {
        //                    newBoard[i+1][j] = block
        //                    newBoard[i][j] = "-"
        //                } else {
        //                    continue
        //                }
        //            }
        //        }
        
        // 이렇게 밑에서 부터 탐색하면서 올라오면서 블록을 내려줘야함
        for j in stride(from: 0, to: n, by: 1) { //열
            var first = 0 //블록이 내려와야할 행 위치
            if newBoard[m-1][j] == "-" {
                first = m-1
            }

            for i in stride(from: m-2, through: 0, by: -1) { //행
                if newBoard[i][j] == "-" {
                    if i > first {
                        first = i
                    }
                } else if newBoard[i+1][j] == "-"{
                    newBoard[first][j] = newBoard[i][j]
                    newBoard[i][j] = "-"
                    first -= 1
                }
            }
        }
    }
    return cnt
}


func splitBoard(_ board: [String]) -> [[String]] {
    var newBoard = [[String]]()
    for b in board  {
        let arr = b.map { String($0) }
        newBoard.append(arr)
    }
    return newBoard
}

print(solution(m, n, board))