링크
https://www.acmicpc.net/problem/23309
풀이
- 1 000 000 1 500 000으로 1.5 10^12 => 시간 초과
- i의 다음 역의 번호와 이전 역 번호를 저장하는 1차원 배열 2개를 생성하여 해당 역의 이전, 다음 번호를 O(1)로 접근할 수 있도록 함
코드
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());
}
}
바른 자세로 코딩합니다 👦🏻💻