프로그래머스 - 표 편집

문제

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

프로그래머스

 

 

 

풀이

cmd가 모두 수행된 후 처음과 비교해서 각 행이 삭제됐는지 알아내야 한다.

그 후 삭제된 행만 X로 바꾸면 된다.

 

실제 배열을 선언하고 삽입, 삭제 연산을 하는 대신 인덱스만으로 연산을 진행한다.

각 행마다 위와 아래에 위치한 행과의 차이를 나타낼 수 있다.

행 번호	up	down
0		1
1	0	2
2	1	3
3	2

 

up, down은 행 번호를 기준으로 위에 있는 행, 아래에 있는 행을 나타낸다.

1번의 경우 up은 0번, down은 2번이다.

 

U 또는 D 명령어는 현재 위치를 up, down을 이용해 바꾸면 된다.

 

C 명령어는 다음을 고려해야 한다.

- 삭제된 행을 저장하는 방법

- 배열을 실제로 삭제하지 않아도 인덱스를 활용해 삭제가 된 것처럼 만드는 방법

- 마지막 행 삭제 시, 바로 위의 행을 선택하는 것

 

최근 삭제된 행은 Z 명령을 통해 복구되므로 스택을 이용해 삭제된 행을 저장한다.

 

특정 행 k를 삭제하는 경우 k행의 위, 아래 행도 서로 연결을 시켜줘야 한다.

k행의 아래행은 k의 위행과 연결해야 한다.

up[down[k]] = up[k]

또한 k행의 위행은 k행의 아래행과 연결해야 한다.

down[up[k]] = down[k]

 

위 연산은 맨 위 행과 맨 아래 양 끝에서도 동작해야 한다.

하지만 위 표에서 up[0]와 down[3]은 존재하지 않는다.

이를 위해서 양 끝에 가상의 공간을 추가해 up[0]와 down[3]의 값을 만들 수 있다.

이를 위해 up, down 리스트를 만들 때 +2만큼 큰 리스트를 만든다.

행 번호	up	down
-1
0	-1	1
1	0	2
2	1	3
3	2	4
4

 

기존 리스트의 첫 번째 행은 임시 공간이 추가된 리스트의 두 번째 행이다. 

따라서 k에 1을 더해준다. 

 

Z 명령어는 스택에서 최근에 삭제된 행을 가져오면 된다.

삭제된 행에는 기존에 연결된 up, down 정보가 들어 있다.

이를 이용해 삭제된 행의 윗행과 아래행을 연결한다.

 

명령을 다 마치면 스택에는 삭제된 행만 남아있다.

이 행들만 X로 표시하면 된다.

 

 

 

코드

python

def solution(n, k, cmd):
    up = [i for i in range(-1, n + 1)]
    down = [i for i in range(1, n + 2)]
    
    k += 1
    del_stack = []
    
    for udcz in cmd:
        if 'U' in udcz:
            for _ in range(int(udcz[2:])):
                k = up[k]
 
        if 'D' in udcz:
            for _ in range(int(udcz[2:])):
                k = down[k]
        
        if 'C' == udcz:
            del_stack.append(k)
            up[down[k]] = up[k]
            down[up[k]] = down[k]
            k = down[k] if down[k] <= n else up[k]
        
        if 'Z' == udcz:
            restore = del_stack.pop()
            down[up[restore]] = restore
            up[down[restore]] = restore
    
    answer = ['O'] * n
    for delete_row in del_stack:
        answer[delete_row - 1] = 'X'
    return "".join(answer)