[프로그래머스] 표 편집

https://programmers.co.kr/learn/courses/30/lessons/81303?language=swift 

코딩테스트 연습 - 표 편집

마치 엑셀에서 표를 편집하는 것 처럼 방향키 이동, 삭제, 되돌리기를 구현하는 문제이다! 

 

정확성 + 효율성까지 보는 문제이기 때문에 코드의 효율도 고려하여 작성해야 한다. 

 

우선 예시를 먼저 보자.

 

n = 8, k = 2, cmd = ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]

 

현재 총 길이 8의 표와 현재위치가 2인 모습을 나타내는 그림을 볼 수 있다.

자 이제 여기서 하나씩 커맨드를 입력하며 현재 위치 / 삭제되는 값 / 복구되는 값들을 고려하며 표를 편집해줘야 한다. 

하나하나 봐보기 앞서서 그냥 인덱스를 삭제하여 관리하는 방법은 좋지 않을 것 같다. 

 

어떤 형태로 구현해야할까 고민하다가, 효율성 부분은 답을 얻기 어려워 검색과 공식 풀이를 참고했다. 

Linked List 형태로 풀이를 해야한다고 하였는데, Linked List라기 보다는 이전 인덱스와 이후 인덱스를 잘 연결하는 방식으로 풀이를 진행할 수 있었다. 

 

우선 이와 같이 index, Up, Down으로 구성하였다. 

 

Up의 경우, 위로 이동시 사용되는 배열이고, Down은 아래로 이동할 때 사용할 배열이다.

자세히 보면 Up과 Down은 범위 밖의 값을 하나씩 가지고 있는 걸 볼 수 있다. 

해당 케이스일 경우에는 별도로 처리해줄 예정이다. 

 

왜냐하면, 맨 위(-1)에서 삭제하게 되면 그저 한 칸만 내려와서 다시 현위치를 잡으면 되지만, 맨 아래에서 삭제했을 경우에는 더 이상 내려갈 곳이 없기에, 한 칸 위로 올려주어 현 위치를 조정해야 할 필요가 있기 때문이다. 

 

이를 참고해서 하나씩 케이스를 봐보자. 

 

1. 아래로 2칸 이동해라. (D 2)

하단으로 이동할 때에는 Down 배열을 사용한다고 이야기 했었다. 

주어진 횟수 만큼 반복하며 한 칸씩 내려가면 되는데 코드로는 다음과 같다. 

for _ in 0..<count {
    now = down[now]
}

down[now]는 항상 now보다 큰 값을 가지고 있기에, 이를 반복하면 인덱스를 늘려 아래로 내려갈 수 있다. 

 

2. 현재 인덱스 삭제 (C)

4번 인덱스의 값을 삭제해주면 되는데 이 때, up과 down의 값들도 바꿔줘야 한다. 

 

// 삭제한 인덱스 보관
stack.append(now)

// 첫 열도 제외
if up[now] != -1 {
    down[up[now]] = down[now]
}

// 마지막 열은 제외
if down[now] != n {
    up[down[now]] = up[now]    
}

// 현재 인덱스가 마지막 인덱스일 경우 한 칸 위로 
// 현재 인덱스가 첫 인덱스일 경우 한 칸 아래로 이동
now = down[now] == n ? up[now] : down[now]

즉 4번으로 중간에 위치해있기에, up[now]는 -1이 아니다. 그렇기에 down의 값을 바꿔주어야 한다. 

up[now]가 인덱스로 들어가는데, 아까 봤던 것 처럼 up[now]는 now 보다 항상 작다는 걸 알 수 있다. 즉 down[up[now]]는 더 이전의 값을 down[now]로 대체함으로써 이후에 내려가는 일을 수행할 때 한 번에 넘어가줄 수 있다. 

 

지금 위의 그림을 보면 down의 3행과 4행이 모두 5인 것을 확인할 수 있는데, 이는 앞선 차례에서 down을 변경했기 때문이다. 이 덕분에 제거된 인덱스는 무시하고 지나갈 수 있게 되었다. 그리고 현재 인덱스는 한 칸 내려가게 된다!

 

3. 위로 3칸 이동해라. (U 3)

위로 올라가는 건 아까 1번에서 내려가는 것을 구현한 것과 유사하다. 

 

for _ in 0..<count {
    now = up[now]
}

 

4. 현재 인덱스 삭제

마찬가지로 이전 방법 처럼 삭제해준다. 마찬가지로 인덱스는 하나 밀려서 현재 위치는 2에 놓이게 된다.

그러면 현재 삭제된 인덱스들을 보관하는 stack에는 [4,1]이 보관되게 된다. 

 

5. 아래로 4칸 이동해라. (D 4)

 

6. 현재 인덱스 삭제 (C)

마지막 인덱스를 지우는 것이기에 위 조건에 맞게 제거 후 인덱스를 재조정해준다. 

그리고 stack에는 [4,1,7]이 담기게 된다. 

 

7. 위로 2칸 이동해라. (U 2)

8. 되돌리기 (Z)

현재 stack은 [4,1,7] 이기에 LIFO에 따라 마지막 원소를 추출해준다.

if let back = stack.popLast() {
    if up[back] != -1 {
        down[up[back]] = back
    }
    if down[back] != n {
        up[down[back]] = back
    }
}

그러면 stack은 [4,1]이 되고, 현재 back은 7이 된다. 이제 up / down의 값을 변경해주면 된다. 하지만 down[7]이 8이기에 up은 변경되지 않는다. 

 

9. 되돌리기 (Z)

현재 stack은 [4,1] 이기에 LIFO에 따라 마지막 원소를 추출해준다.

똑같이 변경해주면 된다. 

 

그러면 현재 4번만 지워진 상태이기에 "OOOOXOOO"이 답이 되는 것을 알 수 있다. 

코드 전문은 아래에 첨부한다!

 

import Foundation

func solution(_ n:Int, _ k:Int, _ cmd:[String]) -> String {
    var result = Array(repeating:"O", count: n)
    var up = [Int](-1..<n), down = [Int](1...n)
    var stack = [Int]()
    var now = k   
        
    for com in cmd {
        let c = com.components(separatedBy: " ")
        
        switch c[0] {
        case "U":
            for _ in 0..<Int(c[1])! {
                now = up[now]    
            }            
        case "D":
            for _ in 0..<Int(c[1])! {
                now = down[now] 
            } 
        case "C":            
            stack.append(now) 
            // 내려갈 때 스킵할 수 있게
            if up[now] != -1 {
                down[up[now]] = down[now]
            }
            // 올라갈 때 스킵할 수 있게
            if down[now] != n {
                up[down[now]] = up[now]
            }
            
            now = down[now] == n ? up[now] : down[now]
        case "Z":
            if let back = stack.popLast() {
                
                if up[back] != -1 {
                    down[up[back]] = back
                }
                if down[back] != n {
                    up[down[back]] = back
                }
            
            }
        default:
            break
        }
        // print(result, stack)
    }
    
    for s in stack {
        result[s] = "X"
    }
    
    return result.joined(separator: "")
}