[스위프트 알고리즘] 프로그래머스: 표 편집

문제

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

코딩테스트 연습 - 표 편집

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

예를 들어 위 표에서 "D 2"를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).

다음으로 "U 3"을 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다.

다음으로 "D 4"를 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다. 5행이 표의 마지막 행 이므로, 이 경우 바로 윗 행을 선택하는 점에 주의합니다.

다음으로 "U 2"를 수행하면 현재 선택된 행은 2행이 됩니다.

위 상태에서 "Z"를 수행할 경우 가장 최근에 제거된 "라이언"이 적힌 행이 원래대로 복구됩니다.

다시한번 "Z"를 수행하면 그 다음으로 최근에 제거된 "콘"이 적힌 행이 원래대로 복구됩니다. 이때, 현재 선택된 행은 바뀌지 않는 점에 주의하세요.

이때, 최종 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 "O", 삭제된 행은 "X"로 표시하면 다음과 같습니다.

처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

풀이

효율성까지 통과하기에 어려운 문제엿습니다ㅠ 다 푸는데 2시간은 걸린것 같네요.. 

 

이 문제를 효율성까지 통과하려면 절대로 O(N) 이상의 시간복잡도가 발생하면 안됩니다. 그래서 양방향 링크드 리스트를 사용해야합니다.

그리고 동시에 기존의 링크드 리스트와는 조금 다르게 구성해야하는 부분들이 있습니다.

 

Node 구조

먼저, 각 노드가 자신의 표 인덱스 정보를 기억하고 있어야합니다. 마지막에 최초의 표에서 달라진 부분만을 표시해야하기 때문입니다.

따라서 노드 자료구조는 다음처럼 구성할 수 있습니다.

 

class Node {
    var data: Int?
    var next: Node?
    var prev: Node?
    
    init(data: Int, next: Node?, prev: Node?) {
        self.data = data
        self.next = next
        self.prev = prev
    }
}

 

data에는 인덱스를 넣고, next와 prev에 자신의 다음, 이전 노드의 참조값을 저장합니다. 

 

링크드리스트

이제 링크드리스트를 구현해야하는데요, 링크드리스트는 다음과 같은 정보를 가지고 있어야합니다.

• 삭제된 행의 정보 (isDeleted)
• 가장 앞 노드의 포인터(head)
• 가장 마지막 노드의 포인터(tail)
• 현재 가리키고 있는 노드(cursor)

그리고 이 문제에서 사용하는 연산은 총 4 종류입니다. 

• 새로운 노드 삽입하기
• 현재 가리키고 있는 노드를 삭제하기 
• 삭제 했던 노드를 원래자리에 복원하기
• 현재 가리키고 있는 노드를 변경하기 

 

노드 삽입

링크드리스트에서 가장 앞을 나타내는 head만을 사용하면 새로운 데이터를 넣을 때마다 가장 마지막 노드까지 탐색해야하는 O(N) 시간복잡도가 발생하기 때문에 tail이라는 포인터를 사용해서 항상 링크드리스트의 마지막을 가리키도록 하고 새로운 노드는 tail의 뒤에 붙여주고 tail을 업데이트 하는 방식으로 진행합니다. 이렇게 하면 삽입연산을 O(1)만에 끝낼 수 있습니다.

 

mutating func append(data: Int, isInitCursor: Bool) {
        let node = Node(data: data, next: nil, prev: nil)
        if isInitCursor { cursor = node }
        
        if head == nil {
            head = node
            tail = node
        } else {
            node.prev = tail
            tail?.next = node
            tail = node
        }
        isDeleted.append(false)
    }

 

노드 삭제

노드의 삭제는 어떤 특정한 노드를 삭제하지 않고, 현재 가리키고 있는 노드를 삭제하는 것으로 연산을 수행할 수 있습니다. 따라서 모든 노드를 탐색하지 않고 cursor에 저장된 참조값을 찾아가 해당 노드의 이전노드와 다음노드를 연결해주는 것으로 이번에도 O(1)만에 삭제 연산을 수행합니다. 그리고 삭제가 끝난 이후에는 해당 노드가 가지고 있던 인덱스 값을 사용하여 해당 행이 삭제되었음을 저장합니다.

 

mutating func remove() -> Node? {
        let delNode = cursor
        
        cursor?.next?.prev = cursor?.prev
        cursor?.prev?.next = cursor?.next
        cursor = delNode?.next == nil ? delNode?.prev : delNode?.next
        
        isDeleted[delNode!.data!] = true
        return delNode
    }

 

노드 복원 

노드의 복원은 아주 간단하게 수행할 수 있습니다. 복원하려고 하는 노드가 가지고 있던 이전노드와 다음노드의 참조값을 그대로 사용하여 복원해줍니다. 그리고 삭제되었던 노드가 다시 복원되었음을 저장합니다.

 

    mutating func restore(node: Node?) {
        node?.prev?.next = node
        node?.next?.prev = node
        isDeleted[node!.data!] = false
    }

 

커서 이동 

커서를 이동할 때는 주어지는 값만큼 포인터를 이동시켜줍니다. 양방향 링크드리스트이기 때문에 위로 올라갈때는 이전 노드들을 탐색하고, 내려갈 때는 다음노드들을 탐색합니다. 문제에서 범위를 벗어나는 이동은 입력되지 않는다고 주어져있기 때문에 따로 예외처리를 하지 않아도 됩니다. 이 연산은 주어지는 이동값 x만큼의 O(x) 연산이 수행됩니다.

 

    mutating func moveUp(to amount: Int) {
        for _ in 0..<amount {
            cursor = cursor?.prev
        }
    }
    
    mutating func moveDown(to amount: Int) {
        for _ in 0..<amount {
            cursor = cursor?.next
        }
    }

 

마지막으로 모든 연산을 수행한 뒤에도 삭제되어 있는 노드들을 구분해서 문자열로 만들어 반환하면 해결됩니다!

 

return table.isDeleted.map({ $0 ? "X" : "O" }).joined(separator: "")

 

카카오 인턴십 코테에서 이 문제를 풀다가 시간이 종료되었는데, 이번에도 역시 엄청 많은 시간이 걸렸습니다. 그래도 덕분에 링크드 리스트도 다시 구현해볼 수 있고 많은 공부가 되었습니다!

 

코드