이번 문제는 표 편집 문제이다.
명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제이며, 세부 사항은 아래와 같다.
명령어는 "U, D, C, Z"로 4개이며,
"U X" 는 현재 선택된 행에서 X칸 위에 있는 행을 선택한다.
"D X" 는 현재 선택도니 행에서 X칸 아래에 있는 행을 선택한다.
"C" 는 현재 선택된 행을 삭제 후 바로 아래 행을 선택한다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택한다.
"Z" 는 가장 최근에 삭제된 해을 원래대로 복구한다. 단, 선택된 행은 바뀌지 않는다.
특별한 제한 사항은 없다. 다만 구해야할 정답은 표의 0행부터 n-1행까지에 해당되는 O,X를 순서대로 이어붙인 문자열 형태로 반환해야 한다. 이게 무슨 내용인지 입출력 예를 통해 알아보자.
n 은 행의 갯수이고, k 는 현재 커서가 위치한 행의 번호이다. 그리고 cmd 는 수행할 명령어 리스트 이다.
이제 입출력 예 1 을 살펴보자.
현재 위치는 2번 행이다. "D 2"로 인해 4번 행으로 이동 후 'C' 명령(삭제)를 하게 되면 그 아래 행인 '네오'가 4번으로 올라오고 커서는 4행에 위치한다.
다음 'U 3'에 의해 4행에서 1행으로 커서를 이동 후 'C'(삭제)를 수행한다. 그러면 1번의 콘은 삭제되고, 2행 어피치가 1행으로 이동하며, 커서는 1행에 있게된다.
다음 'D 4'에 의해 1행에서 5행으로 이동하고 'C'를 수행한다. 이 때, 그 아래에는 남은 행이 없으므로 커서는 4행 튜브를 선택하게 된다.
그 다음 'U 2'에 의해 4행에서 2행으로 이동한다.
그리고 'Z'를 수행하게 되는데, 제일 마지막에 삭제된 5행의 라이언을 복구 한다.
그리고 한번 더 'Z'를 수행하게 되면, 1행의 콘이 복구가 되며, 커서의 위치는 변화가 없기 때문에 제이지(3) 행을 선택하게 된다.
이때 삭제된 행을 X 로 표기하고 남은 행을 O으로 표기하면 위와 같고, 이를 문자열로 변환하면 'OOOOXOOO'이 된다.
특별한 수학적 규칙이나 논리가 필요한 부분은 없다.
바로 코드를 작성해 보자.
첫번째 작성한 코드이다...
먼저 cmd 에서 각 요소들을 확인하고 그에 맞는 코드를 설정해 주었다.
D, U 의 경우, 이동해야할 칸수를 따로 can_move 로 분리해주고, 이 값을 가지고 while문을 돌면서 chart[k] 가 'O' 인 경우에만 이동으로 간주하여 주었다.
이 코드의 한가지 장점 Z(복구)를 실행할때 따로 커서의 위치를 신경쓰지 않아도 된다는 점이다.
하지만, 효율성 테스트에서 떨어졌다. 이유야 뭐... 삭제나 이동 시 'X'를 확인하는데 많은 시간을 소비하는 것으로 판단된다.
해당 문제를 시간내에 해결하기 위해서는 링크드 리스트 자료구조를 이용해야 한다.
위는 링크드 리스트를 구현하기 위해 각 노드들의 정보를 만들어주는 방법이다.
여기서 left는 해당 index 바로 직전, right 는 해당 index 다음이며, 위 문제에 적용하면 바로 윗행, 아래행이 된다.
코드가 길어서 이동과 삭제/복원을 나누었다.
먼저 Node를 이용하여 링크드 리스트를 작성하고, 첫번째 요소와 마지막 요소의 left,right 값은 None 으로 설정해 주었다.
이제 cmd를 반복문을 통해, 각 명령을 수행하면 된다.
추출된 수(i.split()[1])을 이용하여 이동을 하게 되는데, 여기서 중요한 점은 반복문을 통해 해당 횟수 만큼 이동하는 것이다.
이때 이동할 방향은 U 의 경우 위로 올라가기 때문에 table[cursor].left, D 의 경우는 right 를 이용한다.
예를들어 총 4개의 행이 존재한다고 보면, 위와 같이 4개의 노드가 연결된 상태로 리스트가 생성된다.
현재 위치가 0 이고, "D 2"를 명령어로 받았다면, cursor = table[cursor].left 를 2번 실행하게 된다.
첫번째는 0의 right 이므로 1이 되고 그 다음은 1의 right 이므로 2가 된다.
실제 index 는 0 -> 1 로 한칸 이동하였지만, cursor 의 값은 table[0].right , table[table[0]].right 로 총 2번 이동한 것과 동일하게 나타난다.
삭제와 복원은 이동에 비해 좀 더 복잡한 코드를 가진다.
먼저 삭제의 경우 해당 table[cursor]/remove 를 True 로 바꾸어 준다. 그리고 삭제된 cursor 는 stack에 저장해 둔다. 이는 나중에 복원을 위해 사용된다.
만약 위 6개의 노드에서 2번 노드가 삭제되었다고 가정해 보자.
2번 노드의 left, right 는 (1,3) 이다. 즉 1번과 3번에 연결되어 있다.
따라서 끊어진 연결을 이어줘야 하는 노드는 1번과 3번이 된다.
1번 노드의 right 에는 3번 노드를, 3번 노드의 left 에는 1번 노드를 연결해 주면 완성이다.
만약 0번 노드가 삭제된 경우라면? 따로 작업은 필요하지 않다.
왜냐하면 문제의 제한사항에 의해 이동이 불가능한 경우는 주어지지 않기 때문이다.
삭제한 이후에는 현재 커서 위치가 변하게 되는데, 현재 행이 삭제되고 그 바로 아래행이 올라오기 때문에 링크드 리스트에서는 현재 사제된 노드의 right 값이 된다. 하지만 마지막 행이 삭제되었다면, 반대로 left 값이 현재 위치로 바뀌게 된다.
복원의 경우에는 stack[-1] 부터 복원되기 시작한다.
위 6개의 노드에서 5번, 2번 순서로 삭제가 되었다면 2번이 먼저 복원이 된다.
그리고 이때 c 라는 변수가 새로 필요한데, 이는 복원된 노드의 번호이다.
2번 노드가 복원 되었기에 다시 1번과 3번 노드의 right, left 값을 2번으로 수정해주면 된다.
그리고 최종적으로 명령을 수행한 뒤에는 해당 node들의 정보중에 remove 값만 확인하여, False 라면 "O", True라면 "X"를 스트링으로 조합해 반환하면 된다.
'프로그래머스 퀴즈(Python) > level 3' 카테고리의 다른 글
| 23.04.10 파이썬 코딩 퀴즈#213 공 이동 시뮬레이션(프로그래머스 스쿨) (0) | 2023.04.10 |
|---|---|
| 23.04.10 파이썬 코딩 퀴즈#212 금과 은 운반하기(프로그래머스 스쿨) (0) | 2023.04.10 |
| 23.04.05 파이썬 코딩 퀴즈#209 110 옮기기(프로그래머스 스쿨) (0) | 2023.04.05 |
| 23.04.03 파이썬 코딩 퀴즈#208 다단계 칫솔 판매(프로그래머스 스쿨) (0) | 2023.04.03 |
| 23.03.31 파이썬 코딩 퀴즈#207 모두 0으로 만들기(프로그래머스 스쿨) (0) | 2023.03.31 |
