문제 링크

문제 풀이 아이디어

구현?

문제를 읽어보면 기본적인 구현 문제처럼 보입니다. 문제에서 요구하는 바를 코드로 바로 옮기면 되는 것이죠. 하지만 문제를 보면 연속된 데이터의 중간 부분을 삭제하고 삽입하는 작업을 여러번 반복해야 합니다.

보통의 Array를 사용하게 되면 삭제, 삽입 모두 O(N)입니다. 해당 작업을 반복문 내에서 실행하기에는 부담스럽습니다. 따라서 삭제, 삽입이 모두 O(1)인 자료구조를 가지고 구현해야 합니다.

Double Linked List

삭제와 삽입이 모두 O(1)인 자료구조로는 링크드 리스트가 있습니다. 링크드 리스트의 단점으로는 조회할 때 O(N)의 시간복잡도를 가지고 있다는 것인데요.

다만 이 단점은 문제 내에서는 현재 위치를 “커서”로 가지고 있기 때문에 크게 문제가 되지는 않습니다. “커서를 임의의 k 번째 줄로 이동하라”라는 입력이 들어온다면 링크드 리스트의 head 노드부터 k번 탐색해야하기 때문에 문제가 됩니다만, 입력은 항상 “위로 (혹은 아래로) k번 이동하라”라는 식으로 주어지므로 조회에 있어서 시간복잡도 문제가 발생하지 않습니다.

조회 Array로 추가, 삭제는 Double Linked List로

문제는 마지막에 정답 String을 만들 때 입니다. 모든 입력을 처리하고나서 정답 String을 만들기 위해서는 링크드 리스트의 head까지 되돌아 갔다가 다시 마지막 노드까지 1번 순회하면서 삭제되지 않고 남아 있는 노드들을 탐색해야 합니다. n이 최대 1,000,000이고 cmd가 최대 200,000이기 때문에 명령을 수행하는 시간보다 마지막에 정답 String을 만드는데 실행시간이 더 걸릴 수 있는 것이죠.

이 문제는 추가적으로 Array를 하나 만들어서 해결할 수 있습니다. 링크드 리스트의 노드가 index를 가지고 있게 하고 정답을 출력하기 위한 Array를 별도로 만들어두고 삽입, 삭제가 일어날 때마다 노드의 index를 통해 Array에 조회해서 반영하는 것이죠. 이렇게 하면 cmd의 길이에만 실행시간이 영향을 받게 됩니다.

Tip) Array → String: .reduce(””, +) vs .joined(separator:)

제가 개인적으로 겪었던 트러블인데요. 제가 처음에 문제를 풀었을 때는 “.reduce(””, +)”를 사용했는데 계속 시간초과가 났습니다. 도저히 다른 곳에서 실행 시간을 줄일 수 없는데 뭐가 문제인가 생각했습니다.

문제는 “.reduce(””, +)”였습니다. 고차함수 reduce는 범용의 함수입니다. 따라서 뒤에 클로저를 전달할 때 “+”이외에 더 복잡한 로직을 전달할 수도 있습니다. 따라서 매번 연산을 할 때마다 임시 String을 만들어서 하나하나 String을 합칩니다.

반면에 “.joined(separator:)”의 경우는 [String]을 String으로 만드는데 특화된 녀석입니다. reduce보다 복잡한 작업을 할 수 없는 대신 실행시간 측면에서 훨씬 빠릅니다.

상술한 것처럼 n의 길이는 최대 1,000,000입니다. “.reduce(””, +)”와 “.joined(separator:)"의 실행시간이 유의미한 차이를 보일 수 있는 길이입니다. 따라서 [String]을 String으로 합칠 때는 “.joined(separator:)”를 사용합시다!

코드

나머지 설명은 아래 코드를 참고해주세요. 참고로 링크드리스트를 Swift로 구현할 때는 Node를 class로 구현해야 합니다. 내부에 property로 자기자신의 타입을 가지고 있어야 하기 때문입니다. (head, tail)

// 더블 링크드 리스트의 노드
class Node {
    let index: Int
    
    // 각각 앞뒤 노드
    var head: Node?
    var tail: Node?

    init(index: Int) {
        self.index = index
        self.head = nil
        self.tail = nil
    }
}

func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
    
    // 노드들의 배열
    var nodes = [Node]()

    // 노드 만들기
    for i in 0..<n {
        let node = Node(index: i)
        nodes.append(node)
    }

    // 인덱스 순서대로 head, tail 연결하기
    nodes[0].tail = nodes[1]
    for i in 1..<(n - 1) {
        nodes[i].head = nodes[i - 1]
        nodes[i].tail = nodes[i + 1]
    }
    nodes[n - 1].head = nodes[n - 2]

    // 현재 커서의 위치
    var now = nodes[k]
    
    // 삭제한 node는 stack에 저장
    var stack = [Node]()
    
    // 정답 배열
    var ans = Array(repeating: "O", count: n)

    // n칸 만큼 위로
    func up(_ n: Int) {
        for _ in 0..<n {
            now = now.head! //👉 범위를 벗어나는 입력은 없으므로 force unwrapping 가능
        }
    }

    // n칸 만큼 아래로
    func down(_ n: Int) {
        for _ in 0..<n {
            now = now.tail! //👉 범위를 벗어나는 입력은 없으므로 force unwrapping 가능
        }
    }

    // 해당 칸 삭제
    func close() {
        stack.append(now) //👉 실행취소를 대비해서 stack에 넣어둔다
        ans[now.index] = "X" //👉 정답 배열에 삭제 표시
        
        // head와 tail를 연결
        now.head?.tail = now.tail //👉 head의 tail은 now의 tail
        now.tail?.head = now.head //👉 tail의 head는 now의 head
        
        // 커서는 아래칸, 없으면 위칸
        now = now.tail ?? now.head!
    }

    // 실행 취소
    func undo() {
        // stack에서 가장 최근 것 꺼내기
        let latest = stack.popLast()! //👉 복구할 행이 없을때 실행취소 하는 입력은 없으므로 force unwrapping 가능
        ans[latest.index] = "O" //👉 복구
        
        // 원래 head와 tail에 다시 연결
        latest.head?.tail = latest
        latest.tail?.head = latest
    }

    // 명령문 실행
    for cm in cmd {
        let c = cm.first!
        if c == "U" {
            up(Int(cm.split(separator: " ")[1])!)
        } else if c == "D" {
            down(Int(cm.split(separator: " ")[1])!)
        } else if c == "C" {
            close()
        } else if c == "Z" {
            undo()
        }
    }

    // 배열을 String으로 바꾸어서 리턴
    // .reduce("", +)의 비용이 높다.
    return ans.joined()
}