백준 23309번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초 (추가 시간 없음)	512MB (추가 메모리 없음)	골드 4

---

풀이

 중앙에서 삭제와 삽입이 빈번하고, 앞 뒤가 이어져 있으며, 하나의 역에서 이전 원소와 다음 원소를 모두 알고 있어야 한다. 이중 원형 연결리스트 문제이다. 하지만 STL의 list를 곧이 곧대로 사용했다가는 TLE가 날 것만 같은 N과 M의 최댓값이다. 그래서 메모리의 손해를 좀 보고, 이차원 배열에 이중 원형 연결리스트의 개념을 접목시켰다. 모든 역에는 고유번호가 붙기 때문에 이 고유번호를 배열의 인덱스로 잡고, 해당 배열에는 각각 이전 역의 고유번호와 다음 역의 고유 번호를 저장하도록 한다. 고유번호는 100만까지 있고, 각 역은 두개의 고유번호를 저장해야하기에 메모리가 초과될거 같지만, 2백만개의 int형 정수는 8MB밖에 되지 않는다.

 

이제 입력으로 들어오는 쿼리를 연결리스트 동작에 맞게 작성하면 된다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m, q1, q2, tmp;
	string cmd;
	int subway[1000001][2] = {0};
	vector<int> v;

	cin >> n >> m;
	v.resize(n);

	for(int& x : v) cin >> x;

	for(int i = 0; i < n; i++) {
		subway[v[i]][0] = v[(i + n - 1) % n];
		subway[v[i]][1] = v[(i + 1) % n];
	}

	while(m--) {
		cin >> cmd;
		if (cmd[0] == 'B') {
			cin >> q1 >> q2;

			if (cmd[1] == 'N') {
				tmp = subway[q1][1];

				cout << tmp;

				subway[q2][0] = q1;
				subway[q2][1] = tmp;

				subway[q1][1] = q2;
				subway[tmp][0] = q2;
			}
			else if (cmd[1] == 'P') {
				tmp = subway[q1][0];

				cout << tmp;

				subway[q2][0] = tmp;
				subway[q2][1] = q1;

				subway[tmp][1] = q2;
				subway[q1][0] = q2;
			}
		}
		else {
			cin >> q1;

			if (cmd[1] == 'N') {
				tmp = subway[q1][1];

				cout << tmp;

				subway[q1][1] = subway[tmp][1];
				subway[subway[tmp][1]][0] = q1;

				subway[tmp][0] = 0;
				subway[tmp][1] = 0;
			}
			else if (cmd[1] == 'P') {
				tmp = subway[q1][0];

				cout << tmp;

				subway[q1][0] = subway[tmp][0];
				subway[subway[tmp][0]][1] = q1;

				subway[tmp][0] = 0;
				subway[tmp][1] = 0;
			}
		}
		cout << endl;
	}
}