[프로그래머스] Swift - 표 병합

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

프로그래머스

 

2023.09.16 기준 Level 3

 

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

 

아이디어

• 표의 크기는 50 x 50으로 고정
• 명령어
  • UPDATE 2 종류
  • MERGE
  • UNMERGE
  • PRINT

문제 조건 자체는 단순합니다. 마치 엑셀 표에 데이터를 채워 넣고 병합하는 것처럼 2차원 배열의 데이터들의 값을 업데이트하고 cell끼리 병합을 하라는 문제입니다.

 

하지만 프로그래밍의 세계에서 2차원 배열을 물리적으로 병합하는 것은 불가능하기 때문에 다른 방식으로 병합(Merge)를 처리해야 합니다.

다른 분들은 Union-Find 알고리즘을 사용하여 이 문제를 해결한 사례가 많은데 저는 좀 더 구현 풀이법의 측면으로 접근했습니다.

 

접근 방법

라우터라는 새로운 객체를 생성하고 표(2차원 배열)의 각 칸에는 이 라우터가 들어가게 됩니다.

즉, 표의 cell이 곧바로 문제에서 주는 value를 가지는게 아니라 라우터라는 객체를 통해서 value에 접근하게 되는 것입니다.

그림으로 나타내면 다음과 같습니다.

 

이 예시 그림에서 (2,1), (2,2) (4,1)은 병합된 상태입니다.

UPDATE 명령어를 수행할 때는 cell의 값을 바꾸는 것이 아니라 Cell이 가리키는 Router의 value를 바꾸면 됩니다.

 

이 상태에서 (2,1)에 UNMERGE를 수행하면 다음과 같이 됩니다.

 

cell이 가리키는 라우터를 새로 생성하여 EMPTY를 가리키게 합니다.

 

r,c에 해당하는 (2,1)은 기존에 가리키던 Korean을 유지합니다.

 

 

이렇게 라우터라는 중간 다리를 생성하고 이 라우터가 Value를 가지게 되면 병합된 셀들의 값을 업데이트할 때 하나의 Router 객체가 가리키는 값만 수정하면 되기 때문에 효율적입니다.

 

단, Merge와 Unmerge를 수행할 때 두 라우터를 가리키고 있는 좌표들을 전부 하나의 라우터로 몰아줘야 합니다.

예를 들어 MERGE r1 c1 r2 c2 를 수행한다면,

(r1, c1)이 가리키는 router1

(r2,c2)가 가리키는 router2

를 병합해야 합니다.

router1이 Empty가 아닌 value를 가지고 있다면 (r2, c2)를 router1에 병합시켜야 합니다.

이 때 단순히 (r2, c2)의 화살표만 router1으로 바꾸는 것이 아니라!

router2를 가리키던 모든 좌표들의 화살표를  router1로 바꿔야 한다는 뜻입니다.

(기존에 병합된 셀들이기 때문에 같이 움직여야 함)

 

 

 

풀이

1. Router 클래스 구현

fileprivate typealias Coord = (x: Int, y: Int)

fileprivate class Router {
    var value: String
    var inboundCoords = [Coord]()
    var hasValue: Bool {
        return value != "EMPTY"
    }
    
    init(value: String, inboundCoords: [Coord] = []) {
        self.value = value
        self.inboundCoords = inboundCoords
    }
}

Router는 Struct가 아니라 Class로 구현해야 합니다.

2차원 배열의 각 cell이 Router를 가리키기 되는데 병합이 발생하여 여러 셀이 하나의 라우터를 가리켜야 하는 상황이 발생한다면 이 셀에 들어갈 타입이 참조 타임 (reference type)이어야 병합했을 때 각 셀이 메모리상에서 실제로 같은 객체를 가리키게 됩니다.

 

struct라면 동일한 router 객체를 table[x][y]에 넣어도 복사가 발생하여 메모리에서는 결국 다른 공간을 가리키게 되어 병합 로직 처리가 불가능해집니다.

 

inboundCoords 프로퍼티는 라우터 객체를 가리키고 있는 좌표들을 담을 배열입니다.

Merge와 Unmerge 작업에 필요합니다.

 

2.  update 함수 구현

fileprivate func update(table: inout [[Router]], value1: String, value2: String) {
    for i in 0..<51 {
        for j in 0..<51 {
            let router = table[i][j]
            
            if router.value == value1 {
                router.value = value2
            }
        }
    }
}

"UPDATE value1 value2" 명령어를 처리하는 함수 입니다.

각 cell을 탐색하며 router.value가 value1이면 value2로 전부 바꿉니다.

 

다른 명령어를 처리하는 로직은 solution에 몰아 넣었습니다.

사실 update 함수처럼 여러개의 함수로 각 로직을 분리하는 것이 좋습니다. 저는 빠르게 작성하고 채점을 받기 위해 table 전체 탐색을 수행하는 update만 우선 별도의 함수로 분리했습니다.

 

3. solution 함수 구현

fileprivate func solution(_ commands:[String]) -> [String] {
    var table: [[Router]] = []
    var result = [String]()
    
    for i in 0..<51 {
        var routers = [Router]()
        for j in 0..<51 {
            routers.append(Router(value: "EMPTY", inboundCoords: [(i, j)]))
        }
        
        table.append(routers)
    }
    
    for _command in commands {
        let command = _command.components(separatedBy: " ")
        let cmd = command[0]
        
        switch cmd {
        case "UPDATE":
            if command.count == 4 {
                let r = Int(command[1])!
                let c = Int(command[2])!
                let value = command[3]
                let router = table[r][c]
                router.value = value
            } else {
                let value1 = command[1]
                let value2 = command[2]
                update(table: &table, value1: value1, value2: value2)
            }
            
        case "MERGE":
            let r1 = Int(command[1])!
            let c1 = Int(command[2])!
            let r2 = Int(command[3])!
            let c2 = Int(command[4])!
            let router1 = table[r1][c1]
            let router2 = table[r2][c2]
            
            if (r1, c1) == (r2, c2) { break }

            if router1 === router2 { break }
            
            if router1.hasValue && router2.hasValue {
                for (x, y) in router2.inboundCoords {
                    table[x][y] = router1
                }
                router1.inboundCoords.append(contentsOf: router2.inboundCoords)
            } else if router1.hasValue {
                for (x, y) in router2.inboundCoords {
                    table[x][y] = router1
                }
                router1.inboundCoords.append(contentsOf: router2.inboundCoords)
            } else if router2.hasValue {
                for (x, y) in router1.inboundCoords {
                    table[x][y] = router2
                }
                router2.inboundCoords.append(contentsOf: router1.inboundCoords)
            } else {    // 둘 다 EMPTY인 경우에도 Merger가 가능 함
                for (x, y) in router2.inboundCoords {
                    table[x][y] = router1
                }
                router1.inboundCoords.append(contentsOf: router2.inboundCoords)
            }
            
        case "UNMERGE":
            let r = Int(command[1])!
            let c = Int(command[2])!
            let router = table[r][c]
            let value = router.value
            
            for (x, y) in router.inboundCoords {
                let newRouter = Router(value: "EMPTY", inboundCoords: [(x, y)])
                table[x][y] = newRouter
            }
            
            table[r][c].value = value
            
        case "PRINT":
            let r = Int(command[1])!
            let c = Int(command[2])!
            
            result.append(table[r][c].value)
        default:
            break
        }
    }

    return result
}

51 x 51 크기의 2차원 배열 table을 만들었습니다. (50 x 50이 아닌 이유는 문제에서 제공하는 좌표가 0이 아닌 1부터 시작하기 때문!)

정답을 보관한 result 배열을 생성했습니다.

 

table의 초기값을 EMPTY를 가지는 라우터로 채워 넣습니다.

 

commands를 반복문을 돌며 각 명령을 수행합니다.

 

Update

• 해당 위치에 접근하여 router의 value를 새 값을 수정합니다.

Merge

• 문제 조건에 따라 router1과 router2가 같다면 break 합니다.
• Merge 조건에 맞게 한쪽 라우터에 속한 좌표들을 반대쪽 라우터로 몰아주어 병합합니다.

Unmerge

• 해당 좌표가 가리키는 라우터와 이 라우터와 연결된 좌표들의 화살표를 해제합니다. (table[x][y]에 새 EMPTY 라우터를 넣어서 해제!)
• (r,c)의 라우터에는 기존 value를 유지시켜 줍니다.

Print

• (r,c)가 가리키는 라우터의 value를 result에 추가합니다.

 

주의할 점!

Merge를 수행할 때 EMPTY인 Cell들도 병합이 가능해야 합니다!

Merge 명렁어 로직의 마지막 else문을 추가한 이유가 바로 이것입니다.

처음에 EMPTY 끼리도 병합이 가능한지 모르고 해당 로직 없이 채점을 했다가 9번과 15번 이후의 테케에서 많이 실패했습니다.

꼭 이 부분을 처리해주어야 합니다!!

 

 

마무리

특별한 알고리즘적인 테크닉이 없어도 풀 수 있는 문제였습니다.

 

문제 조건에서 commands의 count가 1000이하였고 table의 크기도 50x50으로 비교적 작은 값들이었기 때문에 시간 복잡도가 널널했습니다.

Merge와 Unmerge 작업에서 최대 50*50번의 반복작업이 수행되어 전체 명령어의 최대 연산 횟수는 250 * 1000 이었습니다. (시간 초과 발생 X)

 

Merge와 Unmerge 작업을 수행하기 위해 라우터라는 중간 객체를 설계하고 여러개의 문제 조건을 실수 없이 순차적으로 구현하는 것이 주요했습니다.