문제

연세대학교가 위치한 신촌역이 속한 2호선은 그림과 같이 $N$개의 역이 원형으로 연결되어 있다. 각 역은 고유 번호가 할당돼 있으며 역들의 고유 번호는 서로 다르다. 그리고 특정 역의 다음 역은 시계 방향으로 인접한 역을 의미하고, 이전 역은 반시계 방향으로 인접한 역을 의미한다.

2호선은 지하철 노선들 중 유일한 흑자 노선이다. 때문에 2호선 공사 자금이 넉넉하기에 $M$번의 공사를 거치려고 한다. 각 공사는 다음 4가지 중 하나를 시행한다.

• 고유 번호 $i$를 가진 역의 다음 역의 고유 번호를 출력하고, 그 사이에 고유 번호 $j$인 역을 설립한다.
• 고유 번호 $i$를 가진 역의 이전 역의 고유 번호를 출력하고, 그 사이에 고유 번호 $j$인 역을 설립한다.
• 고유 번호 $i$를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
• 고유 번호 $i$를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.

이 때, 이미 설립한 역은 다시 설립하지 않으며 폐쇄한 역은 다시 설립될 수 있다. 그리고 폐쇄 작업은 현재 설립된 역이 $2$개 이상일 때만 들어온다.

2호선을 공사하는 프로그램을 만들어보자.

입력

첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 $N$과 공사 횟수를 나타내는 양의 정수 $M$이 주어진다. ($1 \le N \le 500\,000$, $1 \le M \le 1\,500\,000$)

두 번째 줄에는 공사를 시작하기 이전에 있는 역의 고유 번호를 시계 방향 순서대로 주어진다. 같은 고유 번호를 가진 역은 주어지지 않는다.

이후 $M$개의 줄에 걸쳐서 공사에 대한 정보를 다음과 같이 주어진다.

• BN $i$ $j$ : 고유 번호 $i$를 가진 역의 다음 역의 고유 번호를 출력하고, 그 사이에 고유 번호 $j$인 역을 설립한다.
• BP $i$ $j$ : 고유 번호 $i$를 가진 역의 이전 역의 고유 번호를 출력하고, 그 사이에 고유 번호 $j$인 역을 설립한다.
• CN $i$ : 고유 번호 $i$를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
• CP $i$ : 고유 번호 $i$를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.

입력으로 들어오는 모든 역의 고유 번호는 $1$ 이상 $1\,000\,000$ 이하의 양의 정수다. 폐쇄 작업은 현재 설립된 역이 $2$개 이상일 때만 들어오며, 이미 설립된 역은 또 설립될 수 없지만 폐쇄된 역은 다시 설립될 수 있다.

출력

각 공사에 대한 출력 값을 $M$개의 줄에 걸쳐서 출력한다.

입출력 예

입력

4 4
2 7 3 5
BN 5 11
BP 3 6
CP 2
CN 7

출력

2
1
0

풀이1

• linkedList 구현 -> 시간 초과
  • find할 때 O(역의 개수)만큼 시간이 소요됨
    ->1000000 1500000 = 1.5 10^12이 소요될 수 있음

import java.io.*;
import java.util.*;
public class Main_BOJ23309 {
	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		Station station = new Station();
		st  = new StringTokenizer(br.readLine());
		
		Node now = null;
		
		while(st.hasMoreTokens()) {
			int number = Integer.parseInt(st.nextToken());
			Node newNode = new Node(number);
			station.add(now,newNode);
			now = newNode;
		}
		while(M-->0) {
			st=new StringTokenizer(br.readLine());
			
			String command = st.nextToken();
			int targetNumber = Integer.parseInt(st.nextToken()),newNumber=-1;
			Node target = station.findNode(targetNumber);
			if(st.hasMoreTokens()) newNumber = Integer.parseInt(st.nextToken());
			
			if(command.equals("BN")) {
				target.next.print();
				Node newNode = new Node(newNumber);
				station.add(target, newNode);
			}else if(command.equals("BP")) {
				target.prev.print();
				Node newNode = new Node(newNumber);
				station.add(target.prev, newNode);
			}else if(command.equals("CN")) {
				target.next.print();
				station.delete(target.next);
			}else {
				target.prev.print();
				station.delete(target.prev);
			}
		}
		System.out.print(sb.toString());
	}
	static class Station{
		Node head;
		Station(){
			head = null;
		}
		Node findNode(int targetNum) {
			Node now = head;
			while(now.number!=targetNum) {
				if(now.number==targetNum)break;
				now = now.next;
			}
			return now;
		}
		void add(Node target, Node newNode) {
			if(target == null) {
				head = newNode;
				newNode.next = newNode.prev = newNode;
				return;
			}
			newNode.prev = target;
			newNode.next = target.next;
			target.next.prev = newNode;
			target.next = newNode;
		}
		void delete(Node target) {
			target.prev.next = target.next;
			target.next.prev = target.prev;
			if(target.number==this.head.number)this.head = target.next;
			target = null;
		}
	}
	static class Node{
		int number;
		Node prev;
		Node next;
		Node(int number){
			this.number = number;
			this.prev = null;
			this.next = null;
		}
		void print() {
			sb.append(this.number+"\n");
		}
	}
}

풀이2

• i의 다음 역의 번호와 이전 역 번호를 저장하는 1차원 배열 2개를 생성하여 해당 역의 이전, 다음 번호를 O(1)로 접근할 수 있도록 함

import java.io.*;
import java.util.*;
public class Main_BOJ23309 {
	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		st  = new StringTokenizer(br.readLine());
		Station station = new Station();
		int target = -1;
		while(st.hasMoreTokens()) {
			int number = Integer.parseInt(st.nextToken());
			station.add(target, number);
			target = number;
		}
		while(M-->0) {
			st=new StringTokenizer(br.readLine());
			
			String command = st.nextToken();
			int targetNumber = Integer.parseInt(st.nextToken()),newNumber=-1;
			if(st.hasMoreTokens()) newNumber = Integer.parseInt(st.nextToken());
			
			if(command.equals("BN")) {
				station.print(station.nextNodes[targetNumber]);
				station.add(targetNumber, newNumber);
			}else if(command.equals("BP")) {
				station.print(station.preNodes[targetNumber]);
				station.add(station.preNodes[targetNumber], newNumber);
			}else if(command.equals("CN")) {
				station.print(station.nextNodes[targetNumber]);
				station.delete(station.nextNodes[targetNumber]);
			}else {
				station.print(station.preNodes[targetNumber]);
				station.delete(station.preNodes[targetNumber]);
			}
		}
		System.out.print(sb.toString());
	}
	static class Station{
		int[] preNodes;
		int[] nextNodes;
		Station(){
			preNodes = new int[1000001];
			nextNodes = new int[1000001];
		}
		void add(int target, int node) {
			if(target==-1) {
				preNodes[node] = nextNodes[node] = node;
				return;
			}
			preNodes[node] = target;
			nextNodes[node] = nextNodes[target];
			preNodes[nextNodes[target]] = node;
			nextNodes[target] = node;
		}
		void delete(int target) {
			preNodes[nextNodes[target]] = preNodes[target];
			nextNodes[preNodes[target]] = nextNodes[target];
		}
		void print(int num) {
			sb.append(num+"\n");
		}
	}
}