[BOJ] 23309번 철도 공사

링크

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

풀이

• 1 000 000 1 500 000으로 1.5 10^12 => 시간 초과
• i의 다음 역의 번호와 이전 역 번호를 저장하는 1차원 배열 2개를 생성하여 해당 역의 이전, 다음 번호를 O(1)로 접근할 수 있도록 함

참고 : https://velog.io/@jihun333/%EB%B0%B1%EC%A4%8023309-%EC%B2%A0%EB%8F%84-%EA%B3%B5%EC%82%AC%EC%9E%90%EB%B0%94

코드

1. 큐 이용한 구현 -> 시간 초과

package Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_23309_철도공사 {
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		Queue<Integer> q = new LinkedList<Integer>();
		ArrayList<Integer> arr = new ArrayList<Integer>();
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i ++) {
			q.add( Integer.parseInt(st.nextToken()) );
		}
		for(int w = 0; w < m; w++) {
			st = new StringTokenizer(br.readLine());
			String type = st.nextToken();
			int before =0 , i = 0, j = 0, tmp;
			switch (type) {
			case "BN":
				//고유 번호 i를 가진 역의 다음 역의 고유번호를 출력하고 그 사이에 고육번호 j를 설립한다.
				i = Integer.parseInt(st.nextToken());
				j = Integer.parseInt(st.nextToken());
				while(true) {
					tmp = q.poll();
					if(tmp == i) {
						q.add(i);
						q.add(j);
						int nx = q.poll();
						System.out.println(nx);
						q.add(nx);
						break;
					}
					q.add(tmp);
				}
				break;
			case "BP":
				//고유 번호 i를 가진 역의 이전 역의 고유번호를 출력하고 그 사이에 고유번호 j를 설립한다.
				i = Integer.parseInt(st.nextToken());
				j = Integer.parseInt(st.nextToken());
				before = q.peek(); //이전 고유번호를 저장할 변수
				while(true) {
					tmp = q.poll();
					if(tmp == i) {
						q.add(j);
						q.add(i);
						System.out.println(before);
						break;
					}
					before=tmp;
					q.add(tmp);
				}
				break;
			case "CN":
				//고유 번호 i를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
				i = Integer.parseInt(st.nextToken());
				while(true) {
					tmp = q.poll();
					if(tmp == i) {
						q.add(i);
						System.out.println(q.poll());
						break;
					}
					before=tmp;
					q.add(tmp);
				}
				break;
			case "CP":
				//고유 번호 i를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
				i = Integer.parseInt(st.nextToken());
				before = q.peek(); //이전 고유번호를 저장할 변수
				while(true) {
					tmp = q.poll();
					if(tmp == i) {
						q.add(i);
						System.out.println(before);
						break;
					}
					q.add(before);
					before=tmp;
				}
				break;
			}
		}
	}
	
}

2. 1차원 배열 2개를 이용했지만 sysout 사용으로 시간초과

package Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_23309_철도공사 {
	public static int[] preNodes = new int[1000001]; //인덱스를 "해당 역의 고유번호"로 하고 값으로 "직전 역의 고유번호"를 가진다.   
	public static int[] postNodes = new int[1000001]; ; //인덱스를 "해당 역의 고유번호"로 하고 값으로 "직후 역의 고유번호"를 가진다.
	public static void add(int target, int node) {
		if(target == -1) {
			preNodes[node]= postNodes[node] = node;
			return;
		}
		preNodes[node] = target;//새로 추가된 node의 직전 노드는 target으로 설정함
		postNodes[node] = postNodes[target]; //target이 가리키던 노드를 새로 추가된 node의 직후 노드로 설정함 
		preNodes[postNodes[target]] = node;//target이 가리키고 있던 노드의 직전 노드를 새로 추가된 node로 설정
		postNodes[target] = node; //target이 가리키는 노드는 새로 추가된 노드로 설정함
	}
	public static void delete(int targetNode) {
		//target의 직전 노드가 가리키는 노드를 target이 가리키는 노드로 설정해야함
		postNodes[preNodes[targetNode]] = postNodes[targetNode];
		//target의 직후 노드의 직전 노드는 target의 직전 노드로 설정해야함
		preNodes[postNodes[targetNode]] = preNodes[targetNode];
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int target = -1;
		for(int i = 0; i < n; i ++) {
			int node = Integer.parseInt(st.nextToken());
			add(target, node);
			target = node;
		}
		for(int w = 0; w < m; w++) {
			st = new StringTokenizer(br.readLine());
			String type = st.nextToken();

			int targetNode = Integer.parseInt(st.nextToken());
			int newNode = 0;
			if(st.hasMoreTokens()) {
				newNode = Integer.parseInt(st.nextToken());
			}
			
			switch (type) {
			case "BN":
				//고유 번호 i를 가진 역의 다음 역의 고유번호를 출력하고 그 사이에 고육번호 j를 설립한다.
				System.out.println(postNodes[targetNode]);
				add(targetNode, newNode);
				break;
			case "BP":
				System.out.println(preNodes[targetNode]);
				add(preNodes[targetNode], newNode);
				break;
			case "CN":
				//고유 번호 i를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
				System.out.println(postNodes[targetNode]);
				delete(postNodes[targetNode]);
				break;
			case "CP":
				//고유 번호 i를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
				System.out.println(preNodes[targetNode]);
				delete(preNodes[targetNode]);
				break;
			}
		}
	}
	
}

3. 'Station' Class 생성하고 StringBuilder 사용으로 성공

package Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_23309_철도공사 {
	static StringBuilder sb = new StringBuilder();
	public static class Station{
		public int[] preNodes; //인덱스를 "해당 역의 고유번호"로 하고 값으로 "직전 역의 고유번호"를 가진다.   
		public int[] postNodes; //인덱스를 "해당 역의 고유번호"로 하고 값으로 "직후 역의 고유번호"를 가진다.
		
		Station() {
			preNodes = new int[1000001];
			postNodes = new int[1000001];
		}
		public void add(int target, int node) {
			if(target == -1) {
				preNodes[node] = postNodes[node] = node;
				return;
			}
			preNodes[node] = target;//새로 추가된 node의 직전 노드는 target으로 설정함
			postNodes[node] = postNodes[target]; //target이 가리키던 노드를 새로 추가된 node의 직후 노드로 설정함 
			preNodes[postNodes[target]] = node;//target이 가리키고 있던 노드의 직전 노드를 새로 추가된 node로 설정
			postNodes[target] = node; //target이 가리키는 노드는 새로 추가된 노드로 설정함
		}
		public void delete(int targetNode) {
			//target의 직전 노드가 가리키는 노드를 target이 가리키는 노드로 설정해야함
			postNodes[preNodes[targetNode]] = postNodes[targetNode];
			//target의 직후 노드의 직전 노드는 target의 직전 노드로 설정해야함
			preNodes[postNodes[targetNode]] = preNodes[targetNode];
		}
		void print(int num) {
			sb.append(num+"\n");
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		Station station = new Station();
		st = new StringTokenizer(br.readLine());
		int target = -1;
		for(int i = 0; i < n; i ++) {
			int node = Integer.parseInt(st.nextToken());
			station.add(target, node);
			target = node;
		}
		for(int w = 0; w < m; w++) {
			st = new StringTokenizer(br.readLine());
			String type = st.nextToken();

			int targetNode = Integer.parseInt(st.nextToken());
			int newNode = 0;
			if(st.hasMoreTokens()) {
				newNode = Integer.parseInt(st.nextToken());
			}
			
			switch (type) {
			case "BN":
				//고유 번호 i를 가진 역의 다음 역의 고유번호를 출력하고 그 사이에 고육번호 j를 설립한다.
				station.print(station.postNodes[targetNode]);
				station.add(targetNode, newNode);
				break;
			case "BP":
				station.print(station.preNodes[targetNode]);
				station.add(station.preNodes[targetNode], newNode);
				break;
			case "CN":
				//고유 번호 i를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
				station.print(station.postNodes[targetNode]);
				station.delete(station.postNodes[targetNode]);
				break;
			case "CP":
				//고유 번호 i를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
				station.print(station.preNodes[targetNode]);
				station.delete(station.preNodes[targetNode]);
				break;
			}
		}
		System.out.println(sb.toString());
	}
	
}