백준 3045번 이중 연결 리스트

문제 링크입니다: https://www.acmicpc.net/problem/3045

3045번: 이중 연결 리스트

블로그 방문하셨던 분이 질문주셨던 문제여서 풀어보기 시작했던 문제였습니다.

처음에는 제목만 보고 이중 연결 리스트만 구현하면 되는줄 알았는데 생각보다 많은 부분을 고려해야 풀 수 있었던 문제였습니다.

 

우선, 이중 연결 리스트가 어떤 식으로 삽입 삭제되는지 A 1 4 연산을 예시로 그림과 함께 설명드리겠습니다.

1. 1번 노드를 떼어내야하기 때문에 1번 노드의 다음 노드인 2번 노드와 전 노드인 dummy 노드를 연결해줍니다.

2. 1번 노드를 4 번 노드 그리고 4번 노드 전에 위치했던 3번 노드와 연결해줍니다. 

3. 3번 노드와 4번 노드도 1번 노드와 연결해줍니다.

A 1 4 예시

 

그럼 이제 본론으로 돌아와 전체적인 알고리즘을 설명드리겠습니다.

1. 이중 연결 리스트를 구조체 배열로 선언하고 0번째 인덱스를 dummy 노드로 선언해 첫 번째 노드를 가르키는 용도로 사용합니다.

2. 명령어를 입력받아 이중 연결리스트를 재구성합니다. (과정은 위 그림 참고)

3. 이중 연결 리스트를 초기 상태로 최소한의 변경으로 바꾸라는 것은 결국 변경된 이중 연결 리스트에서 LIS(Longest Increasing Sequence) 를 찾아 LIS는 유지한 상태에서 나머지 노드를 변경하라는 것과 마찬가지입니다.

3.1 따라서 2번 과정을 통해 재구성된 이중 연결 리스트를 순차적으로 탐색하며 이분탐색(lower_bound)을 통해 현재 노드가 LIS의 마지막 노드가 되는 인덱스를 찾도록 합니다.

3.1.1 cache의 idx 번째 인덱스에는 노드번호, st 배열에는 노드번호를 인덱스로 해서 LIS를 역순으로 trace하도록 합니다.

3.2 3.1 과정을 진행할 때마다 longestIncreasingLength 변수를 업데이트해줍니다.

4. [전체 노드의 개수 - LIS의 길이]가 수행해야하는 연산의 횟수이므로 출력해줍니다.

5. cache 배열과 st 배열을 통해 LIS 배열을 구합니다.

6. 초기 이중 연결 리스트를 구성하기 위해 LIS 배열을 우선 탐색하며 순서가 맞는지 확인합니다.

6.1 순서가 맞지 않을 경우 A 연산을 통해 순서를 맞춰줍니다.

6.2 LIS 배열을 전부 탐색한 이후에는 B 연산을 통해 LIS 이후에 순서를 맞춰줍니다.

 

* 설명이 조금 장황한데 직접 그려보시면 좀 더 이해하기 편하실 것 같습니다!

 

개발환경:Visual Studio 2019

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~