[BOJ/C] 3045 이중 연결 리스트

https://www.acmicpc.net/problem/3045

3045번: 이중 연결 리스트

문제

창영이는 1학년 때 숙제로 했던 이중 연결 리스트 소스를 상근이에게 생일 선물로 보내주었다. 상근이는 드디어 자신이 원하던 기능이 있는 소스를 받게 되어서 매우 기뻤다. 상근이는 하루종일 이 리스트를 가지고 놀려고 한다.

리스트에는 총 N개의 노드가 포함되어 있고, 가장 왼쪽 노드가 1번이며 나머지는 오른쪽으로 갈 수록 1씩 번호가 증가한다. 리스트가 수행할 수 있는 연산은 아래와 같이 2가지이다.
A) 노드 X를 노드 Y의 앞으로 이동
B) 노드 X를 노드 Y의 뒤으로 이동

리스트를 가지고 다 논 다음에는 처음 상태로 다시 만들어야 한다. 따라서, 상근이는 리스트에 연산을 입력할 때 마다 종이에 적어두었다.
상근이가 입력한 연산이 모두 주어졌을 때, 처음 상태로 만들기 위해 리스트가 수행해야 하는 연산을 구하는 프로그램을 작성하시오. 이때, 연산을 되도록 적게 사용해야 한다.

입력

첫째 줄에 노드의 수 N과 연산의 수 M이 주어진다. (2 ≤ N ≤ 500,000, 0 ≤ M ≤ 100,000)
다음 M개 줄에는 상근이가 입력한 연산이 문제 설명에 나온 형식으로 주어진다.

출력

첫째 줄에 처음 상태로 만들기 위해서 필요한 연산의 최솟값을 출력한다. 이 값을 K라고 한다.
다음 K개 줄에는 리스트가 수행해야 하는 연산을 순서대로 출력한다.

---

풀이

필자는 처음 이 문제를 보았을 때, 단순히 이중 연결 리스트를 사용하면 금방 풀 수 있을 줄 알았다.
아직 코린이인 나의 눈에는.. ‘이게 왜 플레티넘 문제일까?’ 싶은 의문이 들었던 것이다.. 물론 이 의문은 5분도 가지 않고 박살났다.

이 문제의 포인트는 LIS 개념을 알고 활용해야 한다.
LIS도 몰랐던 나는 결국 구글링의 힘으로 다른 고수님들의 풀이를 엿 볼 수 밖에 없었다 ;(

https://jaimemin.tistory.com/1487
참고한 코드는 링크 달아 놓겠습니다!

너무 슬펐던 건 C언어 풀이는 하나도 없었다는 것이다. 코테에서 주력으로 쓰이지 않는다는 것은 알지만 아직 나에게 C언어가 가장 익숙한걸 ... 이제 자바 코딩할거다 진짜 서럽다.

step 1 이중 연결 리스트 생성하기
구조체를 사용해 노드를 구성했다. 각 노드는 이전 노드와 오른쪽 노드의 숫자를 가리킨다.
해당 문제는 1부터 N까지 차례대로 노드를 구성하기 때문에 반복문으로 쉽게 만들 수 있었다.
0번 노드는 head 노드로, 원소 접근에 용이하게 하기 위해 추가하였다.

step2 연산 수행하여 이중 연결 리스트 재생성하기
코드를 그림으로 표현해보았다.

이러한 순서로 연산이 수행된다. 코드와 함께 보면 이해가 쉬울 것 이다.

step 3 LIS를 이용해 최소 연산 횟수 구하기
최소 연산 횟수를 구하는 부분에서 LIS를 떠올리기란 쉽지 않았다. 게다가 난 개념 자체도 몰랐으니 더더욱 어려웠다. 그래도 한 번 공부를 하니 적용하기 수월했다.

예를 들어, { 5 2 3 1 4 } 으로 원소가 구성되어 있다면
LIS -> { 2, 3, 4 } 로 3의 길이를 갖는다.
{2, 3, 4}는 이미 정렬되어 있기 때문에 이를 제외한 {1, 5}를 제자리에 맞게 연산을 수행한다면 원소는 다시 처음으로 돌아오게 된다.
즉, N - LIS 의 자리가 맞지 않는 나머지 원소 개수가 최소 연산 횟수가 된다.

Step 4 최소 연산 구하기
최소 연산 횟수를 알았으니 이제 구체적인 연산을 구해야 한다. 연산을 해야 하는 수는 LIS에 포함되지 않는 나머지 원소들이다.

그러므로 루프를 돌며
1) LIS에 없는 원소라면 연산 수행
2) LIS에 있는 원소라면 다음 원소로 넘어간다
즉, LIS를 탐색하며 정렬되지 않은 수들은 연산을 수행해 맞추어 준다는 것이다.

(* LIS의 끝 원소를 편의상 last라고 부르겠다)
이 때 주의할 점은 A연산은 last보다 작은 원소들에 수행, B연산은 last보다 큰 원소들에게 수행한다.
ex) 5 2 3 1 4, LIS = {2, 3, 4}, last = 4
4보다 작은 1은 [ A 1 2 ], 4보다 큰 5는 [ B 5 4 ]
=> 최소 수행 조건이 맞춰진다.

1. LIS를 저장하여 LIS의 끝 원소까지는 A 연산을 수행한다.
예를 들어, 2 1 4 3 5 , LIS = {1, 3, 5}
이후 1부터 LIS의 끝 원소인 5까지 루프를 돌며 => LIS의 포함된 원소가 아니라면 A 연산 수행 [A 원소 원소보다 큰 LIS 원소]

2. LIS 마지막 원소 이후부터는 B 연산 수행
LIS의 끝 원소 + 1부터 N까지 [B 원소, 원소-1]

[ 코드 ]