[알고리즘] 프로그래머스 - 표 편집

프로그래머스 - 표 편집

다른 사람 풀이

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

    return ''.join(["O" if x else "X" for x in exists])

print(solution(8, 2, ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]) == "OOOOXOOO")
print(solution(8, 2, ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]) == "OOXOXOOO")

출처: https://velog.io/@kerri/Swift-Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Lv3-%ED%91%9C-%ED%8E%B8%EC%A7%91-2021-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%B1%84%EC%9A%A9%EC%97%B0%EA%B3%84%ED%98%95-%EC%9D%B8%ED%84%B4%EC%8B%AD

실제 문제 그대로 구현만하면 시간 초과가 난다.
위치가 now일 때 위로 이동한다면 어느 index로 가야하는지, 아래로 가야하면 어느 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

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] 로 바꿔줍니다.