[PS][Swift] 행렬과 연산(2022 Kakao Tech Internship)

.onNext("Volga")·2022년 8월 26일
0

ProblemSolving

목록 보기
12/15

행렬과 연산 문제를 풉니다.

Swift를 사용해서 행렬과 연산 문제를 풀이합니다.

목표

  • Class로 Quadruple Linked List를 구현해봅시다.
  • Class를 사용해서 Deque을 구현해 봅시다.
  • 행렬과 연산 문제를 맞춰봅시다.

풀이

먼저 문제를 간단하게 요약하면

  1. NxM 행렬이 들어온다.
  2. 행렬 연산에는 2가지 방법의 연산이 존재한다.
  3. 첫 번째 연산은 ShiftRow 그리고 두 번째 연산은 Rotate다.
  4. 최대한 효율적으로 위에 언급한 두 가지 연산을 해 낼수 있도록 구현한다.

가 됩니다.

그리고, 다음으로는 문제의 제약 사항을 볼 필요가 있는데 다음과 같습니다.

  • 2 ≤rc의 행 길이(=행렬의 가로 길이) ≤ 50,000
  • rc의 모든 행의 길이는 동일합니다.
  • 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 50,000
  • rc의 모든 열의 길이는 동일합니다.
  • 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 100,000
  • rc[i][j]i+1번째 행 j+1번째 열에 있는 원소를 나타냅니다.
  • 1 ≤ rc[i][j] ≤ 1,000,000
  • 1 ≤ operations의 길이 ≤ 100,000
  • operations의 원소는 "ShiftRow" 혹은 "Rotate"입니다.

여기서 느낄수 있는 것은 제약 사항으로 주어지는 Row, Col의 길이의 단위가 1만 이상의 단위로 꽤나 커질수 있다는 점 입니다.

첫 번째 접근

간단하게 먼저 생각해본 것은, 단순하게 ShiftRow를 어떻게 편하게 할까? 에서 시작을 합니다.

문제에서 주어진 예시를 간단하게 살펴보면

/*
| 1|  2|  3|  4|
| 5|  6|  7|  8|
| 9| 10| 11| 12|
*/

위의 배열같은 그림이 완성이 됩니다.

이 배열에서 row하나 당 하나의 element로 생각해서 Deque을 만들면 어떨까?

라는 생각을 했는데 그림으로 그려보면 다음과 같습니다.

/*
      front
----------------
| 1|  2|  3|  4| - 0번 row
| 5|  6|  7|  8| - 1번 row
| 9| 10| 11| 12| - 2번 row
----------------
       rear
*/

대략 위와 같은 그림이 그려지게 되고 실제로 나머지 원소들이 하나의 row내 에서 Double Linked List로 이어져있다면, 간단하게 심플한 2중 Deque을 구현 해 낼수 있습니다.

하지만 이 방식은, 순전히 ShiftRow연산에 대해서만 생각한 것이기 때문에 Rotate에서는 사용 할 수 없습니다.

예를들어, Rotate연산을 한다 생각하면, 각 행의 양 사이드 들에 의해서 정확하게 Row의 길이 * 2 만큼의 시간복잡도가 매 연산 마다 일어나게 됩니다.

따라서, 이 방법은 시간 초과를 유발 할 수 있고, 문제에서 요구하는 효율성 테스트를 만족하는 코드가 되지 않을 확률이 높습니다.

내 풀이

Linked List를 사용한 Deque을 구현하면 된다 라는 아이디어에서 조금 더 Deque의 사용 범위를 늘리는 방법을 사용했습니다.

/*
      front
----------------
| 1|  2|  3|  4| - 0번 row
| 5|  6|  7|  8| - 1번 row
| 9| 10| 11| 12| - 2번 row
----------------
       rear
*/

기존의 방법은 위처럼 단순하게, row를 큰 Deque의 원소로 생각을 하게 했는데, 이 부분을 조금 더 확장 시켜서

/*
vfront                        vfront 
  |   vfront            vfront   |
  | --------           --------  |
| 1| hfront -  2|  3| - hrear    4| - 0번 row
| 5| hfront -  6|  7| - hrear    8| - 1번 row
| 9| hfront - 10| 11| - hrear   12| - 2번 row
  | --------           --------  |
  |   vrear              vrear   |
vrear                          vrear
*/

위 그림과 같이 양 사이드를 따로 Veritcal Deque으로 만들고, 그 내부의 것들은 Horizontal Deque으로 만들어서 관리하게 만듭니다.(추가적으로 Horizontal Dequefront, rear들은 서로 위, 아래 방향으로 바라보게 만들었습니다.)

이렇게 될 경우 기존의 ShiftRow연산에서 생각한 Deque을 사용한 이득을 거의 그대로 지키는 것과 동시에 Rotate 연산을 사용 할 경우, 단 4번의 넣고 빼는 작업을 통해 빠르게 Rotate를 할 수 있는 장점이 있습니다.

풀이 with Code

우선 문제를 풀기 위해 사용할 class Code를 보겠습니다.
위의 풀이 방식으로 미루어 보았을 때, 수평으로 양 옆을 바라 보는 경우가 존재하고, 이는 수직 역시 마찬가지입니다.
따라서, 4방향을 모두 쓸 수 있도록(다 쓰지 않더라도 필요하면 쓸 수 있게) 만들 필요가 있었습니다.
저는 간단하게 4방향 모두 뚫어 놓는 방식을 사용했습니다.

코드로 보면

class Node {
    var val: Int
    var front: Node? = nil
    var rear: Node? = nil
    var up: Node? = nil
    var down: Node? = nil
    init() {
        val = 0
    }
    init(_ val: Int, _ front: Node?, _ rear: Node?, _ up: Node?, _ down: Node?) {
        self.val = val
        self.front = front
        self.rear = rear
        self.up = up
        self.down = down
    }
    
    
    func popH() {
        if front != nil { front?.rear = rear }
        if rear != nil { rear?.front = front}
    }
    func popV() {
        if up != nil { up?.down = down }
        if down != nil { down?.up = up }
    }
}

위와 같은 코드로 구현이 되는데, 코드를 보면 알 수 있듯, 4방향(rear, front, down, up)의 방향을 가지고 있는 class를 만들어서 쓸 수 있게 됩니다.

특히 popH() 와, popV()는, 각각 Deque의 양 끝(front, rear)에서 바로 앞, 뒤의 원소를 뺄 수 있게끔 해주는 메소드입니다.
정확하게는 해당 원소를 바라보고있는 양 옆의 원소들의 Indicating방향을 서로에게 겨누게 하는 방식으로 구현이 됩니다!

그리고 저러한 Class 를 문제에 적용하게 되면 다음과 같은 코드가 나오게 됩니다.

import Foundation

class Node {
    var val: Int
    var front: Node? = nil
    var rear: Node? = nil
    var up: Node? = nil
    var down: Node? = nil
    init() {
        val = 0
    }
    init(_ val: Int, _ front: Node?, _ rear: Node?, _ up: Node?, _ down: Node?) {
        self.val = val
        self.front = front
        self.rear = rear
        self.up = up
        self.down = down
    }
    
    
    func popH() {
        if front != nil { front?.rear = rear }
        if rear != nil { rear?.front = front}
    }
    func popV() {
        if up != nil { up?.down = down }
        if down != nil { down?.up = up }
    }
}
var front: [Node] = []
var rear: [Node] = []
var sf: Node = Node(), sr: Node = Node(), ef: Node = Node(), er: Node = Node()
var leftFront = Node(), leftRear = Node(), rightFront = Node(), rightRear = Node()

func initQueues(_ r: Int) {
    for i in 0..<r {
        front.append(Node())
        rear.append(Node())
        front[i].rear = rear[i]
        rear[i].front = front[i]
    }
    sf.down = sr
    sr.up = sf
    ef.down = er
    er.up = ef
    
    leftFront.down = leftRear
    leftRear.up = leftFront
    rightFront.down = rightRear
    rightRear.up = rightFront
}

func solution(_ rc:[[Int]], _ operations:[String]) -> [[Int]] {
    var answer: [[Int]] = []
    initQueues(rc.count)
    
    for i in 0..<rc.count {
        for j in 1..<rc[i].count-1 {
            let node = Node()
            node.val = rc[i][j]
            node.front = rear[i].front;
            node.rear = rear[i];
            rear[i].front?.rear = node;
            rear[i].front = node;
        }
        let n = Node()
        n.val = rc[i][0];
        n.up = leftRear.up;
        n.down = leftRear;
        leftRear.up?.down = n;
        leftRear.up = n;

        let v = Node()
        v.val = rc[i][rc[i].count - 1];
        v.up = rightRear.up;
        v.down = rightRear;
        rightRear.up?.down = v;
        rightRear.up = v;
    }
    
    for i in 0..<rc.count {
        front[i].up = sr.up;
        front[i].down = sr;
        sr.up?.down = front[i];
        sr.up = front[i];

        rear[i].down = er;
        rear[i].up = er.up;
        er.up?.down = rear[i];
        er.up = rear[i];
    }
    
    for i in 0..<operations.count {
        if (operations[i] == "ShiftRow") {
            let left = sr.up
            let right = er.up
            sr.up?.popV()
            er.up?.popV()

            left?.up = sf
            left?.down = sf.down
            sf.down?.up = left
            sf.down = left

            right?.up = ef
            right?.down = ef.down
            ef.down?.up = right
            ef.down = right

            let ll = leftRear.up
            let rr = rightRear.up
            leftRear.up?.popV()
            rightRear.up?.popV()

            ll?.up = leftFront
            ll?.down = leftFront.down
            leftFront.down?.up = ll
            leftFront.down = ll

            rr?.up = rightFront
            rr?.down = rightFront.down
            rightFront.down?.up = rr
            rightFront.down = rr
        } else {
            let left = leftFront.down
            leftFront.down?.popV()

            left?.front = sf.down
            left?.rear = sf.down?.rear

            sf.down?.rear?.front = left
            sf.down?.rear = left
//
            let ru = ef.down?.front
            ef.down?.front?.popH()

            ru?.up = rightFront
            ru?.down = rightFront.down

            rightFront.down?.up = ru
            rightFront.down = ru
//
            let rd = rightRear.up
            rightRear.up?.popV()

            rd?.front = er.up?.front
            rd?.rear = er.up

            er.up?.front?.rear = rd;
            er.up?.front = rd;
//
            let ld = sr.up?.rear
            sr.up?.rear?.popH()

            ld?.down = leftRear
            ld?.up = leftRear.up

            leftRear.up?.down = ld
            leftRear.up = ld
        }
    }

    var nd = sf.down
    let end: Node? = sr
    
    var nf: Node? = ef.down
    var left: Node? = leftFront.down
    var right = rightFront.down
    while nd !== end {
        var inp: [Int] = []
        var start = nd?.rear
        inp.append(left?.val ?? 0)
        while start !== nf {
            inp.append(start?.val ?? 0)
            start = start?.rear
        }
        inp.append(right?.val ?? 0)
        answer.append(inp)
        nd = nd?.down
        left = left?.down
        right = right?.down
        nf = nf?.down
    }
    
    return answer
}

결과

후기

코드를 보면 꽤나 무시무시한 양의 코드가 나오는데, 처음 풀 때, IDE없이 푸는 상태라 괜히 디버깅이 까다로울 것 같고 생각보다 단순반복 작업이기 때문에 그대로 써도 되겠다 싶어서 전부 다 썼습니다.
실제 코드 양은 꽤 길긴 하지만 그렇게 복잡한 코드는 아닙니다.

여기서 알아가야할 아이디어는 Rotate연산을 효율적으로 하기 위해 양 사이드를 Deque으로 감싸서 연산할때 사용한 점과, Swift에서는 딱히 라이브러리를 통해 Queue나, Deque을 지원하고 있지 않은 것 같아서 Swift유저들은 Linked List 개념을 간단하게 알아가고 적용하는 방법을 배워가면 좋을 것 같습니다.

문제는 그렇게 어렵지 않았습니다!

profile
iOS 개발자 volga입니다~

0개의 댓글