[프로그래머스] Swift - 기둥과 보 설치

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

프로그래머스

 

2023.08.10 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

설치 조건

• 기둥 (Pillar)
  • 바닥 위에 설치 가능
  • 보의 한쪽 끝 부분 위에 설치 가능
  • 다른 기둥 위에 설치 가능
• 보 (Beam)
  • 한쪽 끝 부붙이 기둥 위일 때 설치 가능
  • 양쪽 끝 부분이 다른 보와 동시에 연결되어 있으면 설치 가능

 

처음 떠올렸던 방식은 build_frame 배열에 주어진 건설 배열을 돌며

 

1. 설치인 경우 ➡️ 해당 기둥이나 보가 위의 조건에 맞는지 확인 ➡️ 맞으면 설치 (O(1))

2. 제거인 경우 ➡️ 해당 기둥이나 보를 제거했을 때 연결된 요소들이 조건을 위반하지 않는지 확인 ➡️ 문제가 없다면 제거 확정 (O(1))

 

이렇게 설치 또는 제거 일 때 해당 build_frame이 가능한지 파악하는 방식이었습니다.

이렇게 구현을 하다 보니 제거일 때 어려움이 생겼습니다.

 

설치인 경우에는 앞서 설치 조건으로 규명된 몇가지만 확인해주면 되지만,

제거인 경우에는 제거 대상 기둥 or 보와 연결된 요소들이 설치 조건에 위배되지 않는지 확인해야 하기 때문입니다.

이 과정에서 고려하지 못하거나 실수로 조건이 하나만 어긋나면 통과하지 못하는 문제가 발생했습니다.

(완전 빡구현 문제가 되어버립니다..)

 

따라서 제거인 경우에는 다른 방식으로 검증하는 것이 효율적이라고 생각했습니다.

제거 대상과 인접한 요소들을 찾고 그 것들이 온전한지 판단하는 것이 아니라 미리 건축물에서 제거를 시키고 건축물의 모든 요소를 반목문을 통해 돌며 이것들이 "설치 조건"에 위배되지 않는지 확인 하는 방식입니다. (O(N^2))

 

비록 시간 복잡도는 증가하지만 검증해야 할 것이 앞서 문제에서 확실하게 제공한 설치 조건만 수행하면 돼서 실수의 여지가 적고 코드의 양도 줄어들게 됩니다.

만약 한 요소(기둥 또는 보를 의미)라도 설치 조건을 위배하는 상태가 된다면 해당 삭제 명령은 불가능하다고 판단하고 다음 명령으로 넘어가면 됩니다.

 

 

 

풀이

우선 기둥과 보의 설치 유무를 나타내기 위한 3차원 어레이를 사용했으며 다음과 같이 선언했습니다.

3차원 어레이를 사용한 이유는 같은 위치에 기둥과 보가 동시에 존재할 수 있기 때문입니다.

var map: [[[Int]]] = Array(repeating: Array(repeating: Array(repeating: 0, count: 2), count: n+1), count: n+1)

map[x][y][a] (a가 0이면 기둥, 1이면 보) 처럼 사용합니다.

만약 map[2][2][0] = 0 이면 (2,2)위치에 기둥이 없다는 의미

map[2][2][0] = 1 이면 (2,2)위치에 기둥이 있다는 의미입니다.

 

1. 기둥 설치 조건에 부합하는지 검증하는 함수 구현

fileprivate func checkPillar(map: [[[Int]]], x: Int, y: Int) -> Bool {
    if y == 0 || map[y-1][x][0] == 1 || map[y][x][1] == 1 || (x-1 >= 0 && map[y][x-1][1] == 1) {
        return true
    }
    
    return false
}

y == 0 는 바닥에 설치를 의미

map[y-1][x][0] == 1 는 기둥위에 설치를 의미

map[y][x][1] == 1 || (x-1 >= 0 && map[y][x-1][1] == 1) 는 보의 한쪽 끝 위에 설치를 의미

 

2. 보 설치 조건에 부합하는지 검증하는 함수 구현

fileprivate func checkBeam(map: [[[Int]]], x: Int, y: Int) -> Bool {
    if map[y-1][x][0] == 1 || (x+1 < map.count && map[y-1][x+1][0] == 1) || (x-1 >= 0 && x < map.count && map[y][x-1][1] == 1 && map[y][x+1][1] == 1) {
        return true
    }
    
    return false
}

 

map[y-1][x][0] == 1 || (x+1 < map.count && map[y-1][x+1][0] == 1) 는 한쪽 끝 부분이 기둥 위인 것을 의미

 

(x-1 >= 0 && x < map.count && map[y][x-1][1] == 1 && map[y][x+1][1] == 1) 는 양쪽 끝이 다른 보와 동시에 연결되어 있음을 의미

 

 

3. 모든 설치된 건축 요소들을 순회하며 문제가 없는지 확인하는 함수 구현

fileprivate func checkEntireMap(n: Int, map: [[[Int]]]) -> Bool {
    for y in 0...n {
        for x in 0...n {
            // 기둥일 때
            if map[y][x][0] == 1 && !checkPillar(map: map, x: x, y: y) {
                return false
            }
            
            // 보일 때
            if map[y][x][1] == 1 && !checkBeam(map: map, x: x, y: y) {
                return false
            }
        }
    }
    
    return true
}

 

4. solution 함수 구현

fileprivate func solution(_ n:Int, _ build_frame: [[Int]]) -> [[Int]] {
    //  map[x][y][a] (a가 0이면 기둥, 1이면 보)
    //  만약 map[2][2][0] = 0 이면 (2,2)위치에 기둥이 없다는 의미
    var map: [[[Int]]] = Array(repeating: Array(repeating: Array(repeating: 0, count: 2), count: n+1), count: n+1)
    
    for buildData in build_frame {
        let x = buildData[0]
        let y = buildData[1]
        let a = buildData[2]
        let isInstall = buildData[3] == 1

        if isInstall {
            // 설치
            if a == 0 {
                if checkPillar(map: map, x: x, y: y) {
                    map[y][x][0] = 1
                }
            } else {
                if checkBeam(map: map, x: x, y: y) {
                    map[y][x][1] = 1
                }
            }
        } else {
            // 삭제
            map[y][x][a] = 0
            if !checkEntireMap(n: n, map: map) {
                map[y][x][a] = 1
            }
        }
    }

    var result = [[Int]]()
    
    for y in 0...n {
        for x in 0...n {
            for a in 0...1 {
                if map[y][x][a] == 1 {
                    result.append([x, y, a])
                }
            }
        }
    }
    
    result = result.sorted(by: {
        if $0[0] == $1[0] {
            if $0[1] == $1[1] {
                return $0[2] < $1[2]
            }
            return $0[1] < $1[1]
        }
        return $0[0] < $1[0]
    })


    return result
}

 

설치 로직에서는 해당 위치에 설치가 가능한지 체크하고 가능하면 map에도 적용시킵니다. O(1) 입니다.

 

삭제 로직에서는 우선 미리 삭제를 시키고 map을 전부 탐색하며 설치 조건에 위배된 요소가 없는지 체크합니다. 위배되었다면 다시 map을 복구시키고 넘어갑니다. O(N^2)입니다.

 

모든 작업이 끝나면 map을 순회하며 설치가된 건축물들을 찾아 result에 넣습니다.

 

문제 조건에 따라

x좌표 오름차순 ➡️ y 좌표 오름 차순 ➡️ 기둥 먼저

이렇게 정렬하고 리턴했습니다.

 

 

마무리

처음에는 꽤 단순한 문제라고 생각했지만 체크해야 하는 조건들이 매우 많아 시간도 오래 걸렸고 머리도 아팠던 문제였습니다.

 

삭제 명령에서 머리를 잘 쓰면 시간복잡도를 낮출 수 있지만 확인해야 하는 조건들이 더 늘어나고 실수할 여지가 커져서 해당 방식이 아닌 전체를 순회하며 문제에서 확실하게 정해준 조건들만 체크하는 방식을 사용했습니다.

 

문제 조건에서 n이 100 이하, build_frame은 1000 이하로 비교적 작은 크기로 제한을 해준 것으로 보아 이러한 문제 풀이 방식도 의도적으로 허용한 것 같습니다.