[BOJ/Gold 4] 백준 23309 철도 공사(C++)

문제 링크

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

23309번: 철도 공사

 

문제

[그림] 2호선 노선도

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

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

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

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

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

 

입력

첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 N과 공사 횟수를 나타내는 양의 정수 M이 주어진다. (1 ≤ N ≤ 500,000, 1 ≤ M ≤ 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개의 줄에 걸쳐서 출력한다.

 

예제 입력 1

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

예제 출력 1

2
7
11
6

 

알고리즘 분류

• 구현

 

풀이

연결 리스트로 구현하려 했는데 시간이 초과되었다.

그래서 이전 역을 기록하는 배열과 다음 역을 기록하는 배열을 만들어서 각 역의 이전 역과 다음 역을 기록해두었다.

역을 설립할 때 BN일 때는 설립한 역의 이전 역은 현재 역, 다음 역은 현재 역의 원래 다음 역으로 기록하고 현재 역의 다음 역은 설립한 역, 현재 역의 원래 다음 역의 이전 역은 설립한 역으로 바꿔주었다.

역을 폐쇄할 때 CN일 때는 현재 역의 다음 역은 폐쇄할 역의 다음 역으로, 퍠쇄할 역의 다음 역의 이전 역은 현재 역으로 바꿔주고 폐쇄할 역의 이전, 다음 역은 모든 역의 고유 번호는 1부터 1,000,000이기 때문에 0으로 바꿔준다.

BP, CP일 때는 BN, CN일 때와 반대로 해준다. 그리고 모든 명령을 수행하기 전에 출력하라고 하는 번호를 출력해준다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, I, J, F;
string Cmd;
vector<int> Vec;
int Prev[MAX];
int Next[MAX];

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> I;
        Vec.push_back(I);
    }
    for (int i = 0; i < N; i++) {
        int Now = Vec[i];
        if (i == 0) {
            Prev[Now] = Vec[N - 1];
            Next[Now] = Vec[1];
        }
        else if (i == N - 1) {
            Prev[Now] = Vec[N - 2];
            Next[Now] = Vec[0];
        }
        else {
            Prev[Now] = Vec[i - 1];
            Next[Now] = Vec[i + 1];
        }
    }
    while (M--) {
        cin >> Cmd;
        if (Cmd == "BN") {
            cin >> I >> J;
            cout << Next[I] << "\n";
            Prev[J] = I;
            Next[J] = Next[I];
            Prev[Next[I]] = J;
            Next[I] = J;
        }
        else if (Cmd == "BP") {
            cin >> I >> J;
            cout << Prev[I] << "\n";
            Prev[J] = Prev[I];
            Next[J] = I;
            Next[Prev[I]] = J;
            Prev[I] = J;
        }
        else if (Cmd == "CN") {
            cin >> I;
            cout << Next[I] << "\n";
            int B = Next[Next[I]];
            Prev[Next[I]] = 0;
            Next[Next[I]] = 0;
            Next[I] = B;
            Prev[B] = I;
        }
        else if (Cmd == "CP") {
            cin >> I;
            cout << Prev[I] << "\n";
            int B = Prev[Prev[I]];
            Prev[Prev[I]] = 0;
            Next[Prev[I]] = 0;
            Prev[I] = B;
            Next[B] = I;
        }
    };
}

int main() {
    FASTIO
    input();

    return 0;
}