카카오 인턴십 3]표 편집 (이중 연결 리스트)

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

코딩테스트 연습 - 표 편집

1.접근

삭제와 삽입 연산이 잦으므로 배열이나 일반 ArrayList가 아닌 LinkedList를 사용해야겠다고 생각했다.

하지만 LinkedList를 이용한 풀이는 시간초과를 받았는데 Up 과 Down이 잦은 문제라 그랬다.

단방향 LinkedList는 한칸 앞(이전 노드)으로 이동하려면 처음(head)부터 리스트를 다시 타고 와야하기 때문에 이중 연결 리스트를 사용해야 한다.

2.풀이

이중 연결 리스트의 특징을 잘 살려서 코드를 짜야한다.

이전 노드를 저장하는 pre_array와 다음 노드를 저장하는 next_array 두개의 배열을 만들어 초기화 해준다.

 

ex) n=5

pre_array=[-1,0,1,2,3] ,next_array=[1,2,3,4,5]

 

다음과 같이 정해주면  (-1~0~1) (0~1~2) (1~2~3) (2~3~4) (3~4~5) 의 다섯 노드가 완성된다.

맨 첫노드 head의 값은 -1로 정해주고 마지막 노드의 꼬리값 tail 은 n으로 정해진다.

이렇게 초기화를 완료했다면 반복문을 통해 명령어를 받으면서

"U" 명령어일때는 왼쪽 링크를 타고 X번 이동하고 "D" 명렁어일때는 오른쪽 링크를 타고 X번 이동한다.

 

중요한건 "C"와 "Z"이다.

"C"명령어가 나오면 현재 인덱스의 노드를 삭제해야한다. 삭제된 노드는 최신순으로 Z에서 불러오므로 Stack에 넣어놓자.

 

C명령어가 나오면 인덱스 이전의 노드의 next값을 현재 삭제해야할 노드의 next값으로 변경해주고

다음 노드의 pre값을 현재 삭제해야할 노드의 pre값으로 변경해주면 삭제가 완료된다

노드 삭제

Z 명령어가 나오면 스택에 들어있는 노드를 후입선출로 가져온다.

스택에서 가져온 인덱스의 next값에 들어있는 pre값을 인덱스의 pre로 설정해주고

인덱스의 pre값에 들어있는 next값을 인덱스의 next값으로 설정해주면 삽입이 완료된다.

노드 삽입

 

3.코드

4.배운점

간만에 자료구조 책을 펴서 이중 연결 리스트를 다시 공부했다. 배워놓고 잘 써먹은적이 없어서 까먹었는데 이번 기회에 잊지 말자.

 

그림출처

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=holy_joon&logNo=221583745847