프로그래머스 - 표 편집 - 2021 카카오 인턴 - swift

 

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

 

문제해설은 이미 카카오테크에 나와있다. 

 

본글은 연결리스트로 푸는 방법과, 세그먼트트리 + 이분탐색 으로 푸는 방법을 작성할것이다. 

 

굉장히 좋은 문제라고 생각한다. 

 

---

 

당시 시험볼때 효율성을 맞추지못한 문제였다.

 

다시 풀어보니, 연결리스트를 이용하니 쉽게 풀리는 문제였다. 

 

우선 문제의 조건에도 핵심이있다. 

마지막에 "모든 X들의 값을 합친 결과가 백만이하인 경우만 입력으로 주어집니다" 가 포인트라고 생각한다.

그 말은, Up, Down은 아무리 많아도 백만이하라는 뜻으로, 이는 완전탐색으로 하나하나 올리거나 내려도 시간에 큰 지장이없다는 뜻이다.

 

다만, C를 진행할때가 문제가된다. 

이미 몇십개, 몇백개, 몇천개 이상이 연속으로 삭제되었다면, 이를 하나하나 탐색하다보면은 시간초과가 날수밖에없다. 

그러므로, 연속적으로 삭제된 구간을 어떻게 빠르게 탐색하냐가 관건인 문제다. 이 부분이 효율성문제이기도하다. 

 

연결리스트 ( 더블연결리스트 )를 이용하면 시간초과를 면할수있다.

각 Node들은 up, down으로 위,아래 Node들을 포인터로 연결시켜준다.

삭제되면 삭제된 Node의 up,down을 연결시켜주면된다.

 

복구하는경우에는 어차피 가장 최근의 삭제된 명령어만 복구하기때문에, 복구하는 Node의 위아래를 자신으로 연결시켜주면된다. 

 

class Node {
    var up: Node?
    var down: Node?
    var idx = 0
}
func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
    
    var node = Node()
    var index = node
    for i in 0..<n-1 {
        node.down = Node()
        node.down?.up = node
        node = node.down!
        node.idx = i+1
        if k == i+1 {
            index = node
        }
    }
    var deleted = [Node]()
    var ans = Array(repeating: "O", count: n)
    
    cmd.forEach {
        let inp = $0.split(separator: " " ).map{String($0)}
        let command = inp[0]
        switch command {
        case "U":
            let num = Int(inp[1])!
            for _ in 0..<num {
                index = index.up!
            }
            
        case "D":
            let num = Int(inp[1])!
            for _ in 0..<num {
                index = index.down!
            }
        case "C":
            index.up?.down = index.down
            index.down?.up = index.up
            deleted.append(index)
            ans[index.idx] = "X"
            if index.down == nil {
                index = index.up!
            } else {
                index = index.down!
            }
        case "Z":
            let restore = deleted.removeLast()
            restore.up?.down = restore
            restore.down?.up = restore
            ans[restore.idx] = "O"
            
        default: print()
        }
    }
    return ans.joined()
}

 

 

 

---

 

 

두번째 접근방법은 세그먼트트리와 이분탐색을 이용한다.

사실 그때 당시 세그먼트트리를 생각하긴 했으나, 내머리로는 못풀거같아서 시도하지 않았었다.

( 세그먼트트리까지만 생각했지 이분탐색까지 응용하자는 생각은 못했다 ㅠ )

 

카카오 해설에는 세그먼트트리와 이분탐색 방법도 있다고 알려주고 있다. 

 

세그먼트트리는 구간별로 빠르게 구간합을 구할수있는 좋은 자료구조다. 

대부분 코딩테스트에서는 잘 나오지는 않지만, 가끔씩 카카오는 나오는 것 같다. 

경험상 카카오에서는 무조건 세그먼트트리를 이용해서 풀어야하는 문제는 없었던 것 같다.

이 문제와 마찬가지로, 여러 접근법중 하나로 풀리는 문제에 속했던 것 같다. 

( 개인적인 생각으로, 이런 문제가 나왔다고해서 아직 코딩테스트를 준비한지 얼마안된 분들이 세그먼트트리를 공부하는건 별로 추천하지않는다. 시간이 많이있다면 세그먼트트리를 공부하는건 굉장히 도움이 된다라고 생각하지만, 시간이 부족한 분들은 전략적으로 공부하는게 더 좋다라고 생각한다. 이런문제는 못풀어도 나만못푸는게 아니라 대부분 못풀수있으니까! ) 

 

구간합이 필요한 이유는, 위에서 잠깐 언급했듯이, 삭제된 연속구간들을 빠르게 지나치기위함이다. 

삭제된 곳들을 0으로 표현하고, 삭제하지않은 곳들을 1로 표현한다.

그러면 x ~ y 의 구간합을 구한다면, 0이상의 값이 나오게되는데, 만약 0이라면, x~y의구간안에는 이동할수있는 곳이 없다는 뜻이된다.

만약 1이상이라면, x~y의 구간안에는 이동할수있는 곳이 여러곳이 존재한다는 뜻이된다. 

 

이분탐색이 필요한 이유는, 현재위치로부터 업,다운을 + Offset만큼 이동하기위해서, 

삭제된 연속구간들을 모두 고려하여, 현재위치+-Offset이 아닌, 현재위치 +- ( Offset + Alpha ) 를 찾아야할 것이다.

Alpha를 찾기위해, 모두 완전탐색한다면 세그먼트트리를 사용하는 이유가 없을것이다. 

그래서 이를 조금더 효율적으로 찾기위해 이분탐색을 이용하여, 적절한(Offset + Alpha)값을 찾아내는 것이다. 

 

연결리스트는 금방 코드를 작성하고 맞았지만, 이 접근법은 맞는데까지 2시간정도 걸렸다.. 

( 세그먼트트리를 너무 오랜만에 보기도했고, 특히나 이분탐색이 좀 어렵기도하다. ) 

 

 

세그먼트트리를 만드는 과정은, O인경우에 1, X인경우에 0을 둠으로써, sum트리를 만들었다. 

만약 특정구간쿼리의 값이 3이라는 뜻은, 그 구간안에 적어도 3칸은 이동할수있다는 뜻이다. ( 삭제되지않았다는 뜻이다 ) 

 

그러므로, 만약 Up 3 명령어를 시행한다고 하면, 

현재위치가 X라고 하면,  left를 0, right를 X-1 로 잡는다. ( findUpper ) 

그리고, left와right를 이분탐색하며, mid를 찾는다.

그래서 세그먼트트리의 쿼리로, mid ~ X-1 까지 구간합을 찾는다.

만약 구간합이 3보다 크거나 같으면, left를 +해준다.  ( left = mid+1 ) 

3보다 작다면, 해당 구간들은 무조건 다 넘어야한다는 뜻으로, right를 -해준다.  ( right = mid-1 ) 

 

( 이 이분탐색의 조건을 제대로 찾는데 시간이 좀 걸렸다. ) 

 

그리고 삭제명령어를 시행할때는 

우선 아래쪽을 먼저 탐색하고 ( findLower) , 찾지못했다면, 위를 찾아주는 식( findUpper ) 이여야한다. 

struct Segment {
    var tree: [Int]
    
    init(_ n: Int ) {
        tree = Array(repeating: 0, count: n*4)
        setup(0, 0, n-1)
    }
    
    mutating func setup(_ node: Int, _ left: Int , _ right: Int ) -> Int {
        if left == right {
            tree[node] = 1
            return tree[node]
        }
        let mid = (left+right)/2
        tree[node] = setup(node*2+1, left, mid) + setup(node*2+2, mid+1, right)
        return tree[node]
    }
    
    func query(_ top: Int, _ bottom: Int , _ node: Int, _ left: Int , _ right : Int ) -> Int {
        if left > bottom || right < top { return 0 }
        if top <= left, right <= bottom {
            return tree[node]
        }
        let mid = (left+right)/2
        
        return query(top, bottom, node*2+1, left, mid) + query(top, bottom, node*2+2, mid+1, right)
    }
    
    mutating func update(_ idx: Int, _ num: Int,  _ node: Int, _ left: Int , _ right : Int ) -> Int {
        if idx < left || right < idx {
            return tree[node]
        }
        if left == right {
            tree[node] = num
            return num
        }
        
        let mid = (left+right)/2
        tree[node] = update(idx, num, node*2+1, left, mid) + update(idx, num, node*2+2, mid+1, right)
        return tree[node]
    }
}

func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
    
    var tree = Segment(n)
    var index = k
    var deleted = [Int]()
    var ans = Array(repeating: "O", count: n)
    
    func findUpper(_ l: Int, _ r: Int, _ num: Int ) {
        var left = l, right = r
        
        while left<=right {
            let mid = (left+right)/2
            let sum = tree.query(mid, index-1, 0, 0, n-1)
            if sum >= num {
                left = mid+1
            } else {
                right = mid-1
            }
        }
        index = right
    }
    
    func findLower(_ l: Int, _ r: Int, _ num: Int ) {
        var left = l, right = r
        while left<=right {
            let mid = (left+right)/2
            let sum = tree.query(index+1, mid, 0, 0, n-1)
            if sum >= num {
                right = mid-1
            } else {
                left = mid+1
            }
        }
        index = left
    }
    cmd.forEach {
        let inp = $0.split(separator: " " ).map{String($0)}
        let command = inp[0]
        switch command {
        case "U":
            let num = Int(inp[1])!
            findUpper(0, index-1, num)
        case "D":
            let num = Int(inp[1])!
            findLower(index+1, n-1, num)
        case "C":
            tree.update(index, 0, 0, 0, n-1)
            ans[index] = "X"
            deleted.append(index)
            let keep = index
            
            findLower(index+1, n-1, 1)
            if index >= n || ans[index] == "X" {
                index = keep
                findUpper(0, index-1, 1)
            }
        case "Z":
            let restore = deleted.removeLast()
            tree.update(restore, 1, 0, 0, n-1)
            ans[restore] = "O"
        default: print()
        }
    }
    return ans.joined()
}