[programmers/Swift] 프렌즈4블록 (2018 Kakao Blind Recruitment 1차)

2018 KAKAO BLIND RECRUITMENT

programmers.co.kr - 코딩테스트연습 - Lv.2 - 2018 KAKAO BLIND RECRUITMENT - 프렌즈4블록 1차

programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록

---

TODO

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

만약 판이 위와 같이 주어질 경우,

라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다.

같은 블록은 여러 2×2에 포함될 수 있으며,

지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

 

 

 

 

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

 

 

 

 

 

 

 

 

 

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면

다시 지워지고 떨어지고를 반복하게 된다.

 

 

 

 

 

 

 

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT

RRFACC

RRRFCC

TRRRAA

TTMMMF

TMMTTJ

 

 

 

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

 

Constraints :

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

Sample Input :

m	n	board
4	5	["CCBDE", "AAADE", "AAABF", "CCBBF"]	
6	6	["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]	

Sample Output :

answer
14
15

Solution.swift :

//
//  Created by Yongwoo Marco on 2020/03/12.
//  Copyright © 2020 Yongwoo Marco Kim. All rights reserved.
//
func solution(_ m:Int, _ n:Int, _ board:[String]) -> Int {
    var b = board.map{ $0.map{ (String($0), 0) } }, isMove = true
    let d = [(0, 0), (1, 0), (0, 1), (1, 1)] // y, x
    
    func check(_ arr: inout [[(String, Int)]]) {
        for y in 0..<arr.count {
            for x in 0..<arr.first!.count {
                if y < arr.count - 1, x < arr.first!.count - 1 {
                    if arr[y+1][x].0 == arr[y][x].0, arr[y][x+1].0 == arr[y][x].0, arr[y][x].0 == arr[y+1][x+1].0, arr[y][x].0 != "0" {
                        for (j, i) in d {
                            arr[y+j][x+i].1 += 1
                        }
                    }
                }
            }
        }
        remove(&arr)
    }
    func remove(_ arr: inout [[(String, Int)]]) {
        for y in 0..<arr.count {
            for x in 0..<arr.first!.count {
                if arr[y][x].1 > 0 {
                    arr[y][x] = ("0", 0)
                }
            }
        }
        isMove = false	// 이동이 있는지 확인하는 flag
        move(&arr)		// 이동이 있음 함수가 끝날때 true / 이동 없음 false
    }
    func move(_ arr: inout [[(String, Int)]]) {
        for x in 0..<arr.first!.count {
            for y in 0..<arr.count-1 {
                if arr[y][x].0 != "0", arr[y+1][x].0 == "0" {
                    isMove = true
                    for z in (1...y+1).reversed() {
                        arr[z][x] = arr[z-1][x]
                        arr[z-1][x] = ("0", 0)
                    }
                }
            }
        }
    }
    
    while isMove {
        check(&b)
    }
    
    return b.reduce(0, { a, b in
        return a + b.filter({ $0.0 == "0" }).count
    })
}

How I tried this :

문제는 몇가지 고민할점 만 제외하면 생각보다 간단한 문제였다.

 

가장 먼저 고민했던점은 겹치는 경우이다.

문제에서 제시된 예제 2번 같은 경우 라이언이 총 7개 블록이 2X2 두개로 겹치는 형태였다.

직관적으론 가능하지만 아무래도 탐색의 형태로 접근할때 배열을 순차적으로 접근할텐데

만약 첫번째 2x2 블록을 지우면 채택되어야 할

두번째 내용의 겹치는 부분이 이미 지워져서 지워야 할지 알수가 없다

 

나의 아이디어는 애초에 주어진 표를 처리가 쉽게 변경할때 

튜플로 Int를 하나씩 더주어 0이 아닌 경우면 지워지는 걸로 바꾸었다.

 

결과적으로 배열을 순차적으로 탐색하며 제거, 블록이동 등의 작업을 해야 하기때문에 

아래와 같이 3개의 동작을 구분해서 풀어보았다.

func solution(_ m:Int, _ n:Int, _ board:[String]) -> Int {
    var b = board.map{ $0.map{ (String($0), 0) } }, isMove = true
    let d = [(0, 0), (1, 0), (0, 1), (1, 1)] // y, x
    
    func check(_ arr: inout [[(String, Int)]]) {
        // 모든 배열을 순차적으로 돌며 
        // 00 == 01 10 11 좌표가 같은 경우 튜플.1에 +1
        
        remove(&arr)
    }
    func remove(_ arr: inout [[(String, Int)]]) {
        // check()에서 더해진 튜플.1이 > 0 인경우 ("0", 0) (제거)
        
        isMove = false	// 이동이 있는지 확인하는 flag
        move(&arr)		// 이동이 있음 함수가 끝날때 true / 이동 없음 false
    }
    func move(_ arr: inout [[(String, Int)]]) {
        // arr[y][x]
        // x 0~arr.count
        // y 0~arr[0].count
        // 2차 배열을 볼때 위에서 아래로 내려오며 y축만 비교
        // 현재 y, x 데이터가 있는데 아래 데이터가 "0" 인경우
        // 0~현재 좌표까지 y 데이터 버블 정렬
    }
    
    while isMove {
        check(&b)
    }
    
    return b 배열에서 튜플.0 == "0" 의 갯수
}

중간에 제거된 블록때문에 위에서 아래로 쌓이는 데이터는 버블 정렬을 

해당 보드가 끝났는지 확인할땐 move 함수에서 블록 이동이 있었는지 isMove  플래그를 이용해서 처리했다.

 

What I got is : 

 

I have to study :

 

문제 해설 : 카카오 해설
문제에 관한 모든 저작권 : https://programmers.co.kr/

프로그래머스