프로그래머스 Lv. 2 Swift 알고리즘 - [1차] 프렌즈4블록

이 문제는 그냥 풀기를 포기했던 문제이다...

처음 문제를 보고 이해는 했다.

1. 다중 배열을 사용하여야 할 것 같고

2. 배열의 [i][j] 기준으로 오른쪽, 아래, 대각선 + 1 칸 값들이 전부 같으면 Boom!

3. 하지만 같은 위치가 겹칠 경우엔 어떻게 하지?

4. 그리고 삭제해버린 부분의 위에 있는 블록들의 위치를 변환해줘야하는데... 이거 어떻게 다 하지...?

라는 스트레스가 밀려왔다.

그래서 그냥 이 문제는 구현까지 가는 것도 포기하고 그냥 구글링했다...(알고리즘은 풀이 많이 보고 복습하는 것도 중요하니까.. ^^)

 

그런데 정말 구글링 해보니 논리의 흐름은 내 생각과 다들 비슷한데 코드를 너무 정리 잘해놓으신 분을 찾았다.

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

Swift 공부: Programmers [1차] 프렌즈4블록 [level2] - 2018 KAKAO BLIND RECRUITMENT

뭔가 그냥 딱.. 바로 이해가 가는 깔끔한 풀이! 나의 머릿속 흐름과 굉장히 유사했기에 나한테 특히 깔끔할지도..!

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 우선 m과 n을 활용하여 행렬의 형태를 잡아준다.
2. 미리 만들어놓은 행렬에 board 값을 넣어주고 각 위치마다 값을 비교한다.
3. 이때 같은 위치값이 중복될 경우 (Set을 활용하여 중복 데이터 제거) 그 값을 제거한다.
4. 이러면 한 번에 중복값을 제외한 부분까지 삭제시킬 수 있다.
5. 사라질 블록들을 0으로 치환하고 arr를 재배치한다.
6. 이때 맨 아래쪽이 0인지 확인하고 아니라면 순차적으로 올라오면서 0인 부분을 확인한다.
7. 가장 큰 0의 위치값을 first로 저장하고 0이 아닌 값을 발견했을 때 그 값을 first의 위치만큼 내려준다.
8. 그리고 원래 값의 위치에 0을 대입해준다.
9. 이를 반복하면 4칸 블록을 다시 찾게 되는데 이따 값이 0인 값들끼리 또 잡히지 않도록 값이 0인 경우 continue를 돌린다.
10. 이를 반복하면 끝

 

 

* 처음 생각한 코드

func solution(_ m:Int, _ n:Int, _ board:[String]) -> Int {
    var arrBoard = Array(repeating: Array(repeating: "0", count: n), count: m)

    for (i, j) in board.enumerated(){
        arrBoard[i] = j.map{String($0)}
    }
    
    return 0
}

딱 여기까지 하고... 구현을 포기했다...

 

 

* 참고한 코드

func solution(_ m:Int, _ n:Int, _ board:[String]) -> Int {
    var pre_answer = 0
    var answer = 0
    var answerArr = [[Int]]()
    var arr = Array(repeating:Array(repeating:"0",count:n),count:m)
    for (i,b) in board.enumerated(){
        arr[i] = b.map{String($0)}
    }

    repeat{
        pre_answer = answer
        //행,열 탐색해서 같은 거 있으면 answerArr에 좌표 넣기
        for i in stride(from:0,to:m-1,by:1){ //행
            for j in stride(from:0,to:n-1,by:1){ //열
                if arr[i][j] == "0" {continue}
                if arr[i][j] == arr[i+1][j] && arr[i][j] == arr[i][j+1] && arr[i][j] == arr[i+1][j+1]{
                    answerArr = answerArr + [[i,j]]+[[i+1,j]]+[[i,j+1]]+[[i+1,j+1]]
                }
            }
        }

        //answerArr 중복 없애기
        answerArr = Array(Set(answerArr))

        //answerArr에 있는 좌표 모두 0 만들기
        answer += answerArr.count
        for i in answerArr{
            arr[i[0]][i[1]] = "0"
        }

        //arr 배열 재배치
        for j in stride(from:0,to:n,by:1){ //열
            var first = 0 //블록이 내려와야할 행 위치
            if arr[m-1][j] == "0" {first = m-1}
            for i in stride(from:m-2,through:0,by:-1){ //행
                if arr[i][j] == "0"{
                    if i>first {first = i }
                }
                else if arr[i+1][j] == "0"{
                    arr[first][j] = arr[i][j]
                    arr[i][j] = "0"
                    first -= 1
                }
            }
        }
        //answerArr 다시 빈 배열 만들기
        answerArr = [[Int]]()
    } while(pre_answer<answer)
    return answer
}

모범 답안을 보고도 그런 생각이 들었다... 이걸 시간내에 어떻게 풀지...? 정말 이건 수학문제와 다를바 없어보인다. 주어진 시간내에 최대한 많은 문제를 풀 수 있도록 오래걸릴거 같으면 과감히 제껴라..! 이런 느낌으로 알고리즘 테스트 준비를 해나가야겠다...

 

 

정리(Today I Learned)

1. 다중배열의 핵심은 결국 for문을 얼마나 잘 쓰고 for 문 이외의 반복문을 얼마나 잘 사용하느냐인것 같다. 또한 코드로만 보면 가독성이 너무 떨어져 어려울 수 있으니 꼭 시각적으로 볼 수 있게 print문을 잘 활용하여 접근해보자.