[백준/BOJ] 백준 3045번 : 이중 연결 리스트

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

3045번: 이중 연결 리스트

 

노드들의 초기 정보를 리스트에 저장하고 리스트에 있는 노드에 대한 위치 정보 iterator를 각각 저장해 놓은 뒤, 이를 이용해 주어지는 노드 연산을 수행했다.

그리고 난 뒤, 연산된 결과에서 가장 긴 증가하는 부분 수열 O(n log n)을 찾아서, 가장 긴 증가하는 부분 수열에 속하는 숫자들은 그대로 두고, 가장 긴 증가하는 부분 수열에 속한 숫자들을 기준으로 인접한 왼쪽 부분과 오른쪽 부분을 순서대로 확인하면서 인접한 부분의 숫자를 처음 상태로 만들기 위한 연산을 확인하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <tuple>
#include <list>
using namespace std;

int n, m;
list<int> nodes;
vector<list<int>::iterator> node_it(500005); //[노드 번호] = 리스트에서 iterator
list<int>::iterator it;
vector<int> output;

vector<int> long_sub_check;
vector<int> long_sub_finish_len(500005);
vector<int>::iterator v_it;

deque<int> long_sub_number; //가장 긴 증가하는 부분 수열에 속하는 숫자들
vector<int> maked(500005, 0); //각 숫자가 제자리에 있는지 체크
vector<tuple<char, int, int>> result;

void Pre() {
	for (int i = 0; i <= n + 1; i++) {
		nodes.push_back(i);
	}

	for (it = nodes.begin(); it != nodes.end(); it++) {
		node_it[*it] = it;
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	Pre(); //초기 노드 정보 초기화

	for (int i = 0; i < m; i++) {
		char order;
		int node1, node2;
		list<int>::iterator node1_it, node2_it;

		cin >> order >> node1 >> node2;

		node1_it = node_it[node1];
		node2_it = node_it[node2];

		if (order == 'A') { //node1을 node2 앞으로 이동

			nodes.erase(node1_it); //node1을 지우고

			node1_it = nodes.insert(node2_it, node1); //node2 앞에 node1을 삽입
			node_it[node1] = node1_it;
		}

		else { //node1을 node2 뒤로 이동
			
			nodes.erase(node1_it); //node1을 지우고

			list<int>::iterator node2_it_next = node2_it;
			node2_it_next++; //node2 위치 다음을 가르키도록 한다

			node1_it = nodes.insert(node2_it_next, node1); //node2 뒤에 node1을 삽입
			node_it[node1] = node1_it;
		}
	}

	for (it = nodes.begin(); it != nodes.end(); it++) {
		if ((*it) == 0 || (*it) == n + 1) {
			continue;
		}
		output.push_back(*it);
	}

	//연산된 결과에서 가장 긴 증가하는 부분 수열 (n log n) 을 찾는다
	for (int i = 0; i < output.size(); i++) {

		v_it = lower_bound(long_sub_check.begin(), long_sub_check.end(), output[i]);

		if (v_it == long_sub_check.end()) {
			long_sub_check.push_back(output[i]);
			long_sub_finish_len[i] = long_sub_check.size();
		}

		else {
			(*v_it) = output[i];
			long_sub_finish_len[i] = v_it - long_sub_check.begin() + 1;
		}
	}

	int check_len = long_sub_check.size();
	for (int i = output.size() - 1; i >= 0; i--) { //뒤에서 부터 확인
		if (check_len == 0) {
			break;
		}

		if (long_sub_finish_len[i] == check_len) {
			long_sub_number.push_front(output[i]); //가장 긴 증가하는 부분 수열에 속하는 숫자로 추가
			maked[output[i]] = 1; //해당 숫자는 제자리에 위치해서 움직일 필요가 없다고 체크
			check_len--;
		}
	}

	for (int i = 0; i < long_sub_number.size(); i++) {
		int here = long_sub_number[i];
		int check_point;

		//인접한 왼쪽 확인
		check_point = here - 1;
		while (check_point >= 1 && maked[check_point] == 0) {

			//check_point를 check_point+1 앞으로 이동
			result.push_back(make_tuple('A', check_point, check_point + 1));

			maked[check_point] = 1;
			check_point--;
		}

		//인접한 오른쪽 확인
		check_point = here + 1;
		while (check_point <= n && maked[check_point] == 0) {

			//check_point를 check_point-1 뒤로 이동
			result.push_back(make_tuple('B', check_point, check_point - 1));

			maked[check_point] = 1;
			check_point++;
		}
	}

	cout << result.size() << "\n";
	for (int i = 0; i < result.size(); i++) {
		cout << get<0>(result[i]) << " " << get<1>(result[i]) << " " << get<2>(result[i]) << "\n";
	}

	return 0;
}