[Swift 알고리즘] 프로그래머스(Lv.3) - 기둥과 보 설치 / 2020 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 기둥과 보 설치" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 기둥과 보 설치

 

---

풀이

이번 문제는 구현 문제입니다.

그것도 고약한 구현 문제입니다.

 

1. map을 생성합니다.

저는 Node 구조체를 생성해서 2차원 Node 배열을 정의했습니다.

struct Node {
    var pillar: Bool = false
    var stick: Bool = false
}

좌표에 기둥과 보가 있는지 체크합니다. 보가 영어로 뭘까요..? ㅎㅎ;;

초기화는 전부 false로 했습니다. 

 

2. build_frame을 하나하나 실행합니다.

입력된 build_frame을 하나하나 실행합니다.

 

저는 일단 실행하고 조건에 맞지 않으면 롤백하는 형식으로 진행했습니다.

왜냐하면 삭제 액션의 조건이 매우 복잡하기 때문인데요.

삭제 하기 전에 삭제 조건을 체크하는 것이 아니라, 일단 삭제를 하고 맵에 조건에 맞지 않는 건축물이 있을 경우 삭제를 취소합니다.

 

삭제 조건보다 존재할 수 있는 조건이 훨씬 간단하기 때문에 구현 난이도가 많이 줄어듭니다.

다만, 맵 전체를 확인해야 하기 때문에 시간 효율성은 낮습니다.

 

기둥이 존재할 수 있는 조건은 아래와 같습니다.

1. 바닥(y == 0)이어야 한다.
2. 다른 기둥 위이다.
3. 보의 한 쪽 끝이다.

 

보가 존재할 수 있는 조건은 아래와 같습니다.

1. 기둥이 왼쪽이나 오른쪽에 하나라도 있어야 한다.
2. 양쪽에 보가 있어야 한다.

 

2-1. 기둥이나 보를 생성합니다.

생성 액션을 살펴보겠습니다.

맵에 기둥이나 보를 생성할 수 있는지 확인합니다.

존재 조건에 맞으면 생성, 아니면 액션을 무시합니다.

 

2-2. 기둥이나 보를 삭제합니다.

위에서 말했듯 삭제는 무조건 실행 후 조건을 체크합니다.

만약 삭제한 뒤 맵에 존재 조건에 맞지 않는 건축물이 있으면 삭제를 취소합니다.

삭제 후 맵의 모든 건축물이 조건에 맞으면 그대로 둡니다.

 

이것을 모든 액션에 대해 반복하면 됩니다.

 

3. 정렬 조건에 맞춰 정렬합니다.

정렬 기준은 아래와 같습니다.

1. x 좌표를 기준으로 오름차순
2. x 좌표가 같을 경우 y 좌표 기준으로 오름차순
3. x, y 좌표가 모두 같을 경우 기둥을 보보다 먼저 배치

맵의 (0, 0)부터 (n, n)까지 체크하며 좌표에 기둥이 있다면 기둥을, 보가 있다면 보를 추가합니다.

이때, 3번 조건에 의해 꼭 기둥 먼저 넣고 보를 넣어야 합니다.

 

기둥과 보를 순서에 맞춰 추가하고 x 좌표를 기준으로 정렬합니다.

y는 2중 반복문으로 구현하여 이미 오름차순 정렬이 되어 있기 때문에 x만 맞춰 정렬하면 됩니다.

 

후기

너무 어려웠고 복잡했고 고약한 문제였습니다.

너무 힘들었고 블로그 글 쓰기도 어렵네요.. ㅎㅎ

 

화이팅입니다.

 

감사합니다!

---

전체 코드

import Foundation

struct Node {
    var pillar: Bool = false
    var stick: Bool = false
}

func checkPillar(_ map: inout [[Node]], x: Int, y: Int) -> Bool {
    //바닥 || 기둥 위 || 보의 왼쪽 위 || 보의 오른쪽 위
    if y == 0 || map[x][y-1].pillar || map[x][y].stick || (x > 0 && map[x-1][y].stick) {
        return true
    } else {
        return false
    }
}

func checkStick(_ map: inout [[Node]], x: Int, y: Int) -> Bool {
    //기둥이 왼쪽이나 오른쪽에 하나라도 있거나
    //양쪽에 보가 있을 때
    if map[x][y-1].pillar || 
        (x+1 < map.count && map[x+1][y-1].pillar) || 
         (x-1 >= 0 && x < map.count && map[x-1][y].stick && map[x+1][y].stick) {
        return true
    } else {
        return false
    }
}

func checkStructures(_ map: inout [[Node]]) -> Bool {
    for i in 0..<map.count {
        for j in 0..<map.count {
            if map[i][j].pillar && !checkPillar(&map, x: i, y: j) {
                return false
            }
            
            if map[i][j].stick && !checkStick(&map, x: i, y: j) {
                return false
            }
        }
    }
    
    return true
}
 
func solution(_ n:Int, _ build_frame:[[Int]]) -> [[Int]] {
    var map: [[Node]] = Array(repeating: [], count: n+1)
    for i in 0...n {
        for _ in 0...n {
            map[i].append(Node(pillar: false, stick: false))
        }
    }
        
    for build in build_frame {
        let x = build[0], y = build[1]
        let structure = build[2]
        let action = build[3]
        
        if action == 0 { //삭제
            if structure == 0 { //기둥
                map[x][y].pillar = false
                if !checkStructures(&map) {
                    map[x][y].pillar = true
                }
            } else { //보
                map[x][y].stick = false
                if !checkStructures(&map) {
                    map[x][y].stick = true
                }
            }
        } else { //추가
            if structure == 0 { //기둥
                 if checkPillar(&map, x: x, y: y) {
                     map[x][y].pillar = true
                 }
            } else { //보
                if checkStick(&map, x: x, y: y) {
                     map[x][y].stick = true
                 }
            }
        }
    }
    
    var result: [[Int]] = []
    //기둥 체크
    for x in 0...n {
        for y in 0...n {
            //기둥 체크
            if map[x][y].pillar {
                result.append([x, y, 0])
            }    
            
            //보 체크
            if map[x][y].stick {
                result.append([x, y, 1])
            }
        }
    }
    
    result.sort { $0[0] < $1[0] }
    
    // print(result)
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.