[Swift 알고리즘] 프로그래머스(Lv.3) - 표 편집 / 2021 카카오 인턴십

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 표 편집" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 표 편집

---

풀이

이번 문제는 더블 링크드 리스트 문제였습니다.

Swift를 이용한 링크드 리스트를 한 번도 구현을 안 해봐서 여러 가지로 당황스러웠던 문제였습니다.

 

1. 더블 링크드 리스트를 이용해야 하는 이유

이 문제가 링크드 리스트를 이용해야 한다는 것은 쉽게 알아낼 수 있었습니다.

배열을 이용한 삽입, 삭제는 O(n)이 걸리기 때문에 시간 초과가 난다고 예상 가능합니다.

Dictionary를 이용한 해시 테이블 접근은 순서가 없기 때문에 불가능 했습니다.

그래서 마지막에 도달한 생각이 링크드 리스트를 사용하자였죠.

 

효율성을 따지는 문제였기 때문에 양방향 이동은 필수였습니다.

 

2. 클래스를 이용해 Node 객체를 만들자

next(down), prev(up)가 필요하기 때문에 자기 참조를 해야합니다.

따라서 Struct가 아닌 Class를 이용해 Node를 만들었습니다.

 

3. 링크드 리스트 구현

링크드 리스트를 구현합니다. 딱히 특이사항은 없습니다.

var linkedList: [Node] = []
for i in 0..<n {
    linkedList.append(Node(up: nil, down: nil, index: i))    
}

linkedList[0].down = linkedList[1]
for i in 1...n-2 {
    linkedList[i].up = linkedList[i-1]
    linkedList[i].down = linkedList[i+1]
}
linkedList[n-1].up = linkedList[n-2]

 

4. 커맨드에 따른 동작을 처리합니다.

4-1. U: times만큼 cursor를 up으로 움직입니다.

주석에도 써있듯이 표 범위 안에서만 숫자가 주어지기 때문에 강제 옵셔널 해제를 했습니다.

만약 해당 조건이 없다면 옵셔널 바인딩을 해야 합니다.

for _ in 0..<times {
    cursor = cursor.up! //범위 안의 input만 주어짐
}

 

4-2. D: times만큼 cursor를 down으로 움직입니다.

내용은 U와 동일합니다.

for _ in 0..<times {
    cursor = cursor.down! //범위 안의 input만 주어짐
}

 

4-3. C: cursor의 노드를 삭제합니다.

삭제 전 result의 index 위치를 X로 변경해줍니다.

Z 커맨드 구현을 위해 cancels 스택에 cursor를 push 해줍니다.

 

cursor의 노드를 삭제하고 이전, 이후의 노드의 up, down을 설정합니다.

cursor.up?.down = cursor.down
cursor.down?.up = cursor.up

cursor가 마지막 행이었다면 1번 up, 마지막 행이 아니라면 1번 down 합니다.

 

4-4. Z: 스택에서 Pop하여 노드를 복구합니다.

링크드 리스트를 이용해야 하는 이유 중 하나인 Z 커맨드입니다.

 

cancels 스택에서 pop을 하여 링크드 리스트에 복구하고 result의 index에 "O"로 업데이트 합니다.

이를 위해 C 커맨드에서 노드 배열인 linkedList에서는 삭제를 안 해준 것입니다.

top.up?.down = top
top.down?.up = top

위 코드처럼 심플하게 복구가 가능한 이유는 역순 복구이기 때문입니다.

0, 1, 2, 3, 4 리스트가 있을 때 2가 삭제되고 1이나 3이 삭제되면 up, down을 이용해 복구가 가능할까? 라는 의문이 있었는데요.

역순으로 복구가 되기 때문에 괜찮다는 결론이 나왔습니다.

 

5. result를 joined() 하여 return 합니다.

String 배열인 result를 String으로 만들어 return 합니다.

 

후기

링크드 리스트를 Swift로 처음 구현해봐서 생각보다 너무 오래 걸린 문제였습니다.

이런 걸 보면 Swift에 대한 이해가 부족한 듯 싶어요... ㅠㅠ

자료구조를 한 번씩 Swift로 구현해 봐야겠습니다.

 

감사합니다!

---

전체 코드

import Foundation

class Node {
    var up: Node?
    var down: Node?
    var index: Int = 0
    
    init(up: Node?, down: Node?, index: Int) {
        self.up = up
        self.down = down
        self.index = index
    }
}

func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
    var result: [String] = Array(repeating: "O", count: n)
    
    var linkedList: [Node] = []
    for i in 0..<n {
        linkedList.append(Node(up: nil, down: nil, index: i))    
    }
    
    linkedList[0].down = linkedList[1]
    for i in 1...n-2 {
        linkedList[i].up = linkedList[i-1]
        linkedList[i].down = linkedList[i+1]
    }
    linkedList[n-1].up = linkedList[n-2]
    
    // for item in linkedList {
    //     print("item: \(item.index) / up: \(item.up?.index) / down: \(item.down?.index)")
    // }
    
    var cursor: Node = linkedList[k]
    
    var cancels: [Node] = []
    for command in cmd {
        let cmdArray = command.components(separatedBy: " ")
        
        switch cmdArray.first {
            case "U":
                let times = Int(cmdArray[1])!    
                for _ in 0..<times {
                    cursor = cursor.up! //범위 안의 input만 주어짐
                }
            case "D":
                let times = Int(cmdArray[1])!    
                for _ in 0..<times {
                    cursor = cursor.down! //범위 안의 input만 주어짐
                }
            case "C":
                result[cursor.index] = "X"
                cancels.append(cursor)
                
                cursor.up?.down = cursor.down
                cursor.down?.up = cursor.up
                if cursor.down == nil { //마지막 행
                    cursor = cursor.up!
                } else {
                    cursor = cursor.down!
                }
            case "Z":
                let top = cancels.popLast()!
                result[top.index] = "O"    
                
                top.up?.down = top
                top.down?.up = top
            default: break
        }
        
        // print("cursor: \(cursor.index)")
    }
    
    return result.joined()
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.