[백준 23309] 철도 공사
https://www.acmicpc.net/problem/23309
문제
연세대학교가 위치한 신촌역이 속한 2호선은 그림과 같이 N개의 역이 원형으로 연결되어 있다. 각 역은 고유 번호가 할당돼 있으며 역들의 고유 번호는 서로 다르다. 그리고 특정 역의 다음 역은 시계 방향으로 인접한 역을 의미하고, 이전 역은 반시계 방향으로 인접한 역을 의미한다.
2호선은 지하철 노선들 중 유일한 흑자 노선이다. 때문에 2호선 공사 자금이 넉넉하기에 M번의 공사를 거치려고 한다. 각 공사는 다음 4가지 중 하나를 시행한다.
- 고유 번호 i 를 가진 역의 다음 역의 고유 번호를 출력하고, 그 사이에 고유 번호 j 인 역을 설립한다.
- 고유 번호 i 를 가진 역의 이전 역의 고유 번호를 출력하고, 그 사이에 고유 번호 j 인 역을 설립한다.
- 고유 번호 i 를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
- 고유 번호 i 를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
이 때, 이미 설립한 역은 다시 설립하지 않으며 폐쇄한 역은 다시 설립될 수 있다. 그리고 폐쇄 작업은 현재 설립된 역이 2개 이상일 때만 들어온다.
2호선을 공사하는 프로그램을 만들어보자.
입력
첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 N과 공사 횟수를 나타내는 양의 정수 M이 주어진다. (1≤N≤, 1≤M≤1)
두 번째 줄에는 공사를 시작하기 이전에 있는 역의 고유 번호를 시계 방향 순서대로 주어진다. 같은 고유 번호를 가진 역은 주어지지 않는다.
이후 M개의 줄에 걸쳐서 공사에 대한 정보를 다음과 같이 주어진다.
- BN i j : 고유 번호 i 를 가진 역의 다음 역의 고유 번호를 출력하고, 그 사이에 고유 번호 j 인 역을 설립한다.
- BP i j : 고유 번호 i 를 가진 역의 이전 역의 고유 번호를 출력하고, 그 사이에 고유 번호 j 인 역을 설립한다.
- CN i : 고유 번호 i 를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
- CP i : 고유 번호 i 를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
입력으로 들어오는 모든 역의 고유 번호는 1이상 1,000,000 이하의 양의 정수다. 폐쇄 작업은 현재 설립된 역이 2개 이상일 때만 들어오며, 이미 설립된 역은 또 설립될 수 없지만 폐쇄된 역은 다시 설립될 수 있다.
출력
각 공사에 대한 출력 값을 M개의 줄에 걸쳐서 출력한다.
아이디어
문제의 조건을 고려했을 때, 최악의 경우 N*M (500,000 * 1,500,000) 회 의 연산이 되어버리기에, 시간초과가 날 것을 예상하여 탐색과 삽입, 삭제 연산 시간복잡도를 최대한 줄여야 했다.
그리하여 처음 생각했던 방식은 아래와 같다.
1. HashMap 을 사용하여 고유 번호를 가진 역 탐색
2. Multi LinkedList 를 구현하여, 고유 번호와 이전, 다음 역의 정보를 가진 Node 탐색
3. LinkedList의 삭제 및 삽입을 이용하여 시간복잡도 최소화
package Baekjoon.LinkedList;
import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class B_23309 {
static int N, M;
static Map<Integer, Node> map = new HashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int headInt = Integer.parseInt(st.nextToken());
Node head = new Node(headInt);
map.put(headInt, head);
Node cur = head;
for(int i=1; i<N; i++) {
int curInt = Integer.parseInt(st.nextToken());
Node next = new Node(curInt);
cur.next = next;
next.prev = cur;
map.put(curInt, next);
cur = next;
}
cur.next = head;
head.prev = cur;
while(M-- > 0) {
st = new StringTokenizer(br.readLine());
String command = st.nextToken();
int i = Integer.parseInt(st.nextToken());
if(command.equals("BN")) {
int j = Integer.parseInt(st.nextToken());
Node newNode = new Node(j);
Node curNode = map.get(i);
Node nextNode = curNode.next;
sb.append(nextNode.value).append("\n");
newNode.next = nextNode;
nextNode.prev = newNode;
curNode.next = newNode;
newNode.prev = curNode;
map.put(j, newNode);
} else if(command.equals("BP")) {
int j = Integer.parseInt(st.nextToken());
Node newNode = new Node(j);
Node curNode = map.get(i);
Node prevNode = curNode.prev;
sb.append(prevNode.value).append("\n");
prevNode.next = newNode;
newNode.prev = prevNode;
newNode.next = curNode;
curNode.prev = newNode;
map.put(j, newNode);
} else if(command.equals("CP")) {
Node curNode = map.get(i);
Node prevNode = curNode.prev;
sb.append(prevNode.value).append("\n");
prevNode.prev.next = curNode;
curNode.prev = prevNode.prev;
map.remove(prevNode.value);
} else if(command.equals("CN")) {
Node curNode = map.get(i);
Node nextNode = curNode.next;
sb.append(nextNode.value).append("\n");
curNode.next = nextNode.next;
nextNode.next.prev = curNode;
map.remove(nextNode.value);
}
}
System.out.println(sb);
}
static class Node {
int value;
Node next;
Node prev;
public Node(int value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
}
그러나, 위 방법 역시 최악의 경우 O(M x N) = (500,000 x 1,000,000) 번의 연산으로 시간 초과가 발생했다.
따라서, 더 시간을 줄일 수 있는 방법을 찾아야 했다.
각 역의 고유번호는 겹치지 않는 다는 점에서, LinkedList의 prev 와 next 를 1차원 배열로 접근하여 확실한 O(1)의 연산을 수행하였더니, 아슬아슬하게 통과했다.
LinkedList 역시, O(1)의 탐색 및 삽입 연산을 제공하지만, 내부적으로 오버헤드 발생과, 배열의 압도적인 인덱스 접근 속도 덕분에 시간복잡도를 해결한 문제인 것 같다.
앞으로도, LinkedList 구현에도 시간 복잡도가 우려되면 고정 배열로써의 구현도 고려해보자.
정답 코드
package Baekjoon.LinkedList;
import java.io.*;
public class B_23309 {
static int N, M;
static int[] nextStations = new int[1000001];
static int[] prevStations = new int[1000001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String[] inputs = br.readLine().split(" ");
N = Integer.parseInt(inputs[0]);
M = Integer.parseInt(inputs[1]);
inputs = br.readLine().split(" ");
int headStation = Integer.parseInt(inputs[0]);
int curStation = headStation;
for(int i=1; i<N; i++) {
int nextStation = Integer.parseInt(inputs[i]);
nextStations[curStation] = nextStation;
prevStations[nextStation] = curStation;
curStation = nextStation;
}
prevStations[headStation] = curStation;
nextStations[curStation] = headStation;
while(M-- > 0) {
inputs = br.readLine().split(" ");
String command = inputs[0];
int i = Integer.parseInt(inputs[1]);
if(command.equals("BN")) {
int j = Integer.parseInt(inputs[2]);
int originNextStation = nextStations[i];
sb.append(originNextStation).append("\n");
nextStations[i] = j;
prevStations[j] = i;
nextStations[j] = originNextStation;
prevStations[originNextStation] = j;
} else if(command.equals("BP")) {
int j = Integer.parseInt(inputs[2]);
int originPrevStation = prevStations[i];
sb.append(originPrevStation).append("\n");
prevStations[i] = j;
nextStations[j] = i;
prevStations[j] = originPrevStation;
nextStations[originPrevStation] = j;
} else if(command.equals("CP")) {
int removeStation = prevStations[i];
sb.append(removeStation).append("\n");
int grandPrevStation = prevStations[removeStation];
nextStations[grandPrevStation] = i;
prevStations[i] = grandPrevStation;
} else if(command.equals("CN")) {
int removeStation = nextStations[i];
sb.append(removeStation).append("\n");
int grandNextStation = nextStations[removeStation];
nextStations[i] = grandNextStation;
prevStations[grandNextStation] = i;
}
}
System.out.println(sb);
}
}