문제 설명

당신은 표 편집 프로그램을 작성하고 있습니다. 표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다. 각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.

위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.

"UPDATE r c value"
- (r, c) 위치의 셀을 선택합니다.
- 선택한 셀의 값을 value로 바꿉니다.
"UPDATE value1 value2"
- value1을 값으로 가지고 있는 모든 셀을 선택합니다.
- 선택한 셀의 값을 value2로 바꿉니다.
"MERGE r1 c1 r2 c2"
- (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다.
- 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
- 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다.
- 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
- 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
- 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.
"UNMERGE r c"
- (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다.
- 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
- 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.
"PRINT r c"
- (r, c) 위치의 셀을 선택하여 셀의 값을 출력합니다.
- 선택한 셀이 비어있을 경우 "EMPTY"를 출력합니다.

아래는 UPDATE 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.

commands	효과
UPDATE 1 1 menu	(1,1)에 “menu” 입력
UPDATE 1 2 category	(1,2)에 “category” 입력
UPDATE 2 1 bibimbap	(2,1)에 “bibimbap” 입력
UPDATE 2 2 korean	(2,2)에 “korean” 입력
UPDATE 2 3 rice	(2,3)에 “rice” 입력
UPDATE 3 1 ramyeon	(3,1)에 “ramyeon” 입력
UPDATE 3 2 korean	(3,2)에 “korean” 입력
UPDATE 3 3 noodle	(3,3)에 “noodle” 입력
UPDATE 3 4 instant	(3,4)에 “instant” 입력
UPDATE 4 1 pasta	(4,1)에 “pasta” 입력
UPDATE 4 2 italian	(4,2)에 “italian” 입력
UPDATE 4 3 noodle	(4,3)에 “noodle” 입력

위 명령어를 실행하면 아래 그림과 같은 상태가 됩니다.

아래는 MERGE 명령어를 실행하여 셀을 병합하는 예시입니다.

commands	효과
MERGE 1 2 1 3	(1,2)와 (1,3) 병합
MERGE 1 3 1 4	(1,3)과 (1,4) 병합

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

병합한 셀은 "category" 값을 가지게 되며 (1,2), (1,3), (1,4) 중 어느 위치를 선택하더라도 접근할 수 있습니다.

아래는 UPDATE 명령어를 실행하여 셀의 값을 변경하는 예시입니다.

commands	효과
UPDATE korean hansik	“korean”을 “hansik”으로 변경
UPDATE 1 3 group	(1,3) 위치의 셀 값을 “group”으로 변경

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

아래는 UNMERGE 명령어를 실행하여 셀의 병합을 해제하는 예시입니다.

commands	효과
UNMERGE 1 4	셀 병합 해제 후 원래 값은 (1,4)가 가짐

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ commands의 길이 ≤ 1,000
commands의 각 원소는 아래 5가지 형태 중 하나입니다.
1. "UPDATE r c value"
  - r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
  - value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
2. "UPDATE value1 value2"
  - value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.
3. "MERGE r1 c1 r2 c2"
  - r1, c1, r2, c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
4. "UNMERGE r c"
  - r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
5. "PRINT r c"
  - r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.
commands는 1개 이상의 "PRINT r c" 명령어를 포함하고 있습니다.

풀이

2023 카카오 블라인드 채용 코딩 테스트 5번 문제입니다. 기존에 유니온 파인드 문제를 접해보았다면 해당 유형의 문제임을 쉽게 알 수 있는 문제였고, 카카오가 꾸준히 출시하고 있는 유형이기도 합니다. 다만 기존 유니온 파인드 문제와는 차별되는 한 가지 조건이 있는데, 바로 UNMERGE 동작이 있다는 것입니다.

기존에 유니온 파인드 자료구조의 동작 과정을 정확히 이해하고 있다면 생각보다 어렵지 않게 기존 자료구조를 커스텀하여 UNMERGE 기능을 구현해낼 수 있습니다. 유니온 파인드가 분리 집합 기능을 제공할 수 있는 가장 큰 원리의 핵심은 각 노드의 부모 노드를 관리한다는 것입니다. 주로 이 부모 노드들은 리스트 형태로 관리되는데, MERGE 과정에서 일어난 부모 노드의 변경 사항을 다시 되돌려주기만 하면 UNMERGE 기능을 구현할 수 있습니다.

예를 들어 parent[r][c]가 (r, c) 위치의 부모 셀을 의미할 때, parent[r][c]를 다시 자기 자신으로 초기화 시켜주면 병합을 취소할 수 있습니다. 따라서 (r, c) 위치의 셀을 UNMERGE 하려면 (r, c)와 같은 부모 노드를 갖는 모든 셀들에 대해 부모 노드를 초기화 시켜주면 됩니다. 이 때 주의할 점은, 모든 셀들을 탐색하는 과정에서 (r, c)와 같은 부모 노드를 갖는 셀을 찾았을 때 바로 초기화 시켜주면 안된다는 것입니다. 바로 수정하게 되면 불변성이 깨지면서 부모 노드에 대한 정보가 꼬일 수 있기 때문입니다. 따라서 부모 노드를 초기화 해야 할 노드들을 따로 리스트에 저장해 둔 뒤, 탐색이 끝난 후에 한 번에 초기화 시켜주어야 합니다.

이 외에도 본 문제는 높은 구현력을 요구하는 문제입니다. 유니온 파인드를 이용해 분리 집합 기능을 구현한 뒤에는, UPDATE, MERGE, UNMERGE 동작에 따라 표의 값이 어떻게 바뀌는지 문제의 조건을 참고하여 꼼꼼히 구현해야 합니다.

전체 코드

class Solution {
    fun solution(commands: Array<String>): Array<String> {
        val answer = mutableListOf<String>()
        
        val N = 50
        val board = Array(N + 1) { Array<String>(N + 1) { "EMPTY" } }
        val uf = UnionFind(N)
        
        for(command in commands) {
            val cmd = command.split(" ")
            when(cmd[0]) {
                "UPDATE" -> {
                    if(cmd.size == 4) {
                        val p = uf.find(cmd[1].toInt(), cmd[2].toInt())
                        board[p.r][p.c] = cmd[3]
                    }
                    else {
                        for(i in 1..N) for(j in 1..N) {
                            val p = uf.find(i, j)
                            if(board[p.r][p.c] == cmd[1])
                                board[p.r][p.c] = cmd[2]
                        }
                    }
                }
                "MERGE" -> {
                    val p1 = uf.find(cmd[1].toInt(), cmd[2].toInt())
                    val p2 = uf.find(cmd[3].toInt(), cmd[4].toInt())
                    if(p1 != p2) {
                        val str = 
                            if(board[p1.r][p1.c] != "EMPTY") board[p1.r][p1.c]
                            else board[p2.r][p2.c]
                        uf.merge(p1, p2)
                        val p = uf.find(cmd[1].toInt(), cmd[2].toInt())
                        board[p.r][p.c] = str
                    }
                }
                "UNMERGE" -> {
                    val p = uf.find(cmd[1].toInt(), cmd[2].toInt())
                    val str = board[p.r][p.c]
                    val cells = uf.unmerge(p)
                    for(cell in cells) board[cell.r][cell.c] = "EMPTY"
                    board[cmd[1].toInt()][cmd[2].toInt()] = str
                }
                "PRINT" -> {
                    val p = uf.find(cmd[1].toInt(), cmd[2].toInt())
                    answer.add(board[p.r][p.c])
                }
            }
        }
        
        return answer.toTypedArray()
    }
}

class UnionFind(val n: Int) {
    
    val parent = Array(n + 1) { r -> Array<Point>(n + 1) { c -> Point(r, c) } }
    val rank = Array(n + 1) { IntArray(n + 1) { 1 } }
    
    fun find(r: Int, c: Int): Point {
        if(parent[r][c] == Point(r, c)) return Point(r, c)
        parent[r][c] = find(parent[r][c].r, parent[r][c].c)
        return parent[r][c]
    }
    
    fun merge(_p1: Point, _p2: Point) {
        val p1 = find(_p1.r, _p1.c)
        val p2 = find(_p2.r, _p2.c)
        if(p1 == p2) return
        if(rank[p1.r][p1.c] < rank[p2.r][p2.c])
            parent[p1.r][p1.c] = Point(p2.r, p2.c)
        else {
            parent[p2.r][p2.c] = Point(p1.r, p1.c)
            if(rank[p1.r][p1.c] == rank[p2.r][p2.c])
                rank[p1.r][p1.c]++
        }
    }
    
    fun unmerge(_p: Point): List<Point> {
        val result = mutableListOf<Point>()
        val p = find(_p.r, _p.c)
        for(i in 1..n) for(j in 1..n)
            if(find(i, j) == p)
                result.add(Point(i, j))
        for(p in result) parent[p.r][p.c] = p
        return result
    }
}

data class Point(
    val r: Int,
    val c: Int
)

Android Developer

[2023 카카오 블라인드] 표 병합 풀이 (프로그래머스)

문제 설명

제한사항

풀이

전체 코드