[Swift / Python] 프로그래머스(Lv3) - 표 편집 (2021 카카오 채용연계형 인턴십)

안녕하세요 !

2021 상반기 카카오 채용연계형 인턴십 문제가 프로그래머스에 공개 되었네요 😄

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

풀이

이 문제는 일단 cmd를 무조건 for문으로 수행해야 되는데 cmd의 개수가 최대 200,000 입니다.
그럼 이 문제는 O(n^2)로 풀면 무조건 시간초과가 납니다.
배열이 될 n이 최대 1,000,000 이므로 이 문제는 O(n)에 근사하도록 풀어야 합니다.
즉, for문은 cmd만 도는 것으로 해결하도록 해야합니다.
위치가 now일때 now의 위에 있는 index가 무엇인지, now의 아래에 있는 index는 무엇인지를 저장하는 배열을 이용하여 문제를 풉니다.

index	up	down 				up	down
0	-1	1				-1	1
1	0	2				0	2
2	1	3				1	4
3	2	4	-> index 3을 삭제 -> 	2	4
4	3	5				2	5
5	4	6				4	6
6	5	7				5	7

이렇게 up과 down 배열을 만든다음 이를 이용해서 cmd를 수행합니다.

1. U 연산
U연산일 때 위로 가야하는 cnt 수 만큼 위를 찾아나갑니다. now 위치에서 up[now]를 반복해서 찾아나가면 됩니다.
(now -> up[now] -> up[up[now]] ...)
2. D 연산
아래로 가야하는 cnt 수 만큼 아래를 찾아나갑니다. down 위치에서 down[now]를 반복해서 찾아나가면 됩니다.
(down -> down[now] -> down[down[now]] ...)
3. C 연산
삭제연산이므로 exist[now]를 false로 만들어줍니다. 삭제한 index를 저장하는 delete stack에 now를 추가합니다.
now가 맨 윗행이 아니라면 down[up[now]] = down[now] 로 바꿔줍니다.
now가 맨 아래행이 아니라면 up[down[now]] = up[now] 로 바꿔줍니다.
삭제된 행이 가장 마지막 행이면 now = up[now] 로
마지막 행이 아니라면 now = down[now] 로 바꿔줍니다.
4. Z 연산
delete stack에서 마지막 index를 값을 가져옵니다.
exist[idx] = true 로 바꿔줍니다.
idx가 맨 윗행이 아니라면 down[up[idx]] = down[idx] 로 바꿔줍니다.
idx 맨 아래행이 아니라면 up[down[idx]] = up[idx] 로 바꿔줍니다.

swift 코드입니다.

import Foundation

func solution(_ n: Int, _ k: Int, _ cmds: [String]) -> String {
    var exist = [Bool](repeating: true, count: n)
    var up = [Int](-1...n-1)
    var down = [Int](1...n)
    var delete = [Int]()
    var now = k
    
    for cmd in cmds {
        let op = cmd.components(separatedBy: " ")
        if op[0] == "U" {
            let cnt = Int(op[1])!
            for _ in 0..<cnt {
                now = up[now]
            }
        } else if op[0] == "D" {
            let cnt = Int(op[1])!
            for _ in 0..<cnt {
                now = down[now]
            }
        } else if op[0] == "C" {
            exist[now] = false
            delete.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]
        } else if op[0] == "Z" {
            let idx = delete.popLast()!
            exist[idx] = true
            if up[idx] != -1 {
                down[up[idx]] = idx
            }
            if down[idx] != n {
                up[down[idx]] = idx
            }
        }
        
    }
    
    return exist.map { $0 ? "O" : "X" }.joined()
}

Python 코드입니다.

def solution(n, k, cmd):
    exists = [True for _ in range(n)]
    up = [-1] + [x for x in range(n - 1)]
    down = [x for x in range(1, n)] + [-1]
    deleted = []
    
    for c in cmd:
        op = c[0]
        
        if op == 'U':
            val = int(c.split()[1])
            for _ in range(val):
                k = up[k]
                
        elif op == 'D':
            val = int(c.split()[1])
            for _ in range(val):
                k = down[k]
                
        elif op == 'C':
            if up[k] != -1:
                down[up[k]] = down[k]
            if down[k] != -1:
                up[down[k]] = up[k]
            exists[k] = False
            deleted.append(k)
            k = down[k] if down[k] != -1 else up[k]
            
        elif op == 'Z':
            d = deleted.pop()
            if up[d] != -1:
                down[up[d]] = d
            if down[d] != -1:
                up[down[d]] = d
            exists[d] = True
            
        else:
            raise RuntimeError(op)
    
    return ''.join(['O' if x else 'X' for x in exists])