[Programmers] 표 편집 - swift (Level 3)

문제 1 

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

프로그래머스

문제 요약 

아래 그림의 표와 선택된 행이 있습니다. 이 표를  총 4가지의 명령어를 이용해서 편집하고 난 후, 기존의 표와 달라진 점을 찾는 문제입니다. 4가지 명령어는 아래와 같습니다.

U x : 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다. 

D x : 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.

C : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.

Z : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

 

풀이

연결리스트 자료구조를 이용하는 문제입니다. 포토샵, 문서작업 툴과 같은 상황에서 제거하고 제거한 내용을 복원할 수 있다는 문제라면 자료구조를 연결리스트를 의심해보아야 합니다. Swift에서 연결리스트는 C/C++과 달리 양 옆 노드를 포인터가 아닌 클래스를 가리키도록 합니다. 아래는 2번의 풀이시도에 대한 내용을 작성했습니다. 

첫 번째

배열을 이용하여 실제 표를 만든 다음, 배열의 값을 삭제하고 복구하면서 진행하면 시간 초과가 나올 수 밖에 없습니다. 명령어는 최대 200,000개이고, 표는 최대 1,000,000개의 행을 가질 수 있으며 배열의 삭제와 삽입은 O(N)의 시간복잡도를 가지고 있으니 1000억이 넘는 시간이 걸립니다. 

따라서, n개의 배열을 이용해서 삭제 / 복구를 하지 않고 삭제 여부만 판단했습니다. 삭제와 복구가 이루어지지 않으니 배열을 수정하는 시간을 아낄 수 있고, U, D, C 명령어에서 삭제여부를 판단하여 선택된 행을 수정하면 됩니다. 

코드 

결과

하지만 시간 초과가 나옵니다. 이유를 생각해보면, 삭제여부를 판단하는 시간이 최악의 경우 1,000,000개를 전부 탐색해야하니 1000억이 넘는 시간이 걸려 배열의 삭제와 복구와 다를 바가 없어집니다.

효율성 테스트 시간 초과

두 번째

배열을 이용하지 않고 양방향 연결리스트를 이용할 수 있습니다. 양방향 연결리스트의 삭제와 삽입 시간복잡도는 O(1)이므로 시간을 단축시킬 수 있습니다.

 

양방향 연결리스트를 이용해서 마지막 남은 연결리스트를 구할 수 있습니다. 이 마지막 연결리스트를 이용해서 기존 표와 달라진 점을 구하기 위해서 표의 행을 나타내는 숫자 데이터를 저장해야 합니다. 

 

아래 코드는 처음 표의 상태와 마지막 표의 상태를 비교하여 정답을 구하는 코드입니다.

코드 

결과

정답!

통과했습니다!

 

.

.

.

.

.

cf) 단방향과 양방향 연결리스트의 장단점 정리 

단방향 연결리스트

장점:

배열보다 메모리를 효율적으로 사용 가능합니다. 

배열보다 추가와 삭제가 많은 작업에서 유리합니다. 

단점:

특정 위치의 데이터를 검색하기 위해서 처음부터 끝까지 순회해야 합니다. (비효율적인 시간)

양방향 연결리스트

장점:

단방향 연결리스트의 1번과 동일 

단방향 연결리스트보다 탐색 시간이 절반으로 감소합니다. 

단점:

단방향 연결리스트보다 메모리를 더 많이 사용합니다