[백준 알고리즘]23309번 자바(Java) 철도공사

조건

문제

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

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

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

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

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

 

입력

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

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

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

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

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

출력

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

 

풀이

시간 제한이 2초이고  주어진 N과 M의 최댓값이 50만, 100만 이다보니 시간복잡도O(n^2)방법은 제외를 해야한다.
단순하게 queue를 이용해서 하는방법은 포기해야한다. 

그래서 생각한것이 해당역에 전역과 다음역을 저장하는 배열을 만드는방법이다.

참고로 고유번호가 100만이하의 정수이다 보니 2단 배열로 이전역과 다음역을 받아오면 메모리가 초과될수있다. 

따라서 1단 배열 2개 preArr과 postArr을 2개만드는 식으로 코드를 짰다. 

그래서 preArr과 postArr에 전역과 다음역 고유번호를 넣어주고

M만큼의 공사를 진행하는식으로 풀어봤다.

 

예제 입력 예시

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

 

소스코드

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

//23309번

public class Main {
    public static void main(String[] args) throws IOException {
        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());
        //2단 배열로 만들어서 시간초과난거같음 -> 그래서 1단 배열로 전역과 다음역을 나타내는 역 2개만듬
        int[] preArr = new int [1000001];
        int[] postArr = new int [1000001];

        //첫역 넣기
        int firstStation = Integer.parseInt(st.nextToken());
        int prevStation = firstStation;

        //두번째역부터 마지막역 전까지 넣기
        for (int i = 1; i < N-1; i++) {
            int station = Integer.parseInt(st.nextToken());
            preArr[station] = prevStation;
            postArr[prevStation] = station;
            prevStation = station;
        }
        //마지막역 넣기
        int LastStation = Integer.parseInt(st.nextToken());
        postArr[prevStation] = LastStation;
        preArr[LastStation] = prevStation;
        postArr[LastStation] = firstStation;
        preArr[firstStation] = LastStation;

        StringBuilder sb = new StringBuilder();
        //이제 이전역과 다음역이 정리된 역배열을 토대로 공사시작
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            int curStation = Integer.parseInt(st.nextToken());
            if(str.contains("BN")){  //BN일시 다음역 고유번호 출력후 그 사이에 고유번호 j인 역 생성
                int newStation = Integer.parseInt(st.nextToken());
                int nextStation = postArr[curStation];
                sb.append(nextStation).append("\n");
                //arr[newStation][0]=현재역 [1]= arr[curSation][1] 로 설정한다
                //현재역의 다음역을 newStation으로 설정 그리고
                //그러면 다음역의 이전역을 새로운 역으로 설정 arr[arr[curSation][1]][0] = newStation
                postArr[curStation] = newStation;
                preArr[newStation] = curStation;
                postArr[newStation] = nextStation;
                preArr[nextStation] = newStation;
            }
            else if(str.contains("BP")){  //BP일시 이전역 고유번호 출력후 그 사이에 고유번호 j인 역 생성
                int newStation = Integer.parseInt(st.nextToken());
                int beStation = preArr[curStation];
                sb.append(beStation).append("\n");
                //이전역의 [1] = newStation이 되고
                //newSation[0] = 이전역,   [1] = curStation
                //curSation[0] =  newStation이 된다.
                postArr[beStation] = newStation;
                preArr[newStation] = beStation;
                postArr[newStation]  = curStation;
                preArr[curStation] = newStation;
            }
            else if(str.contains("CN")){  //CN일시 다음역 폐쇄 후 그 역 번호 출력
                //폐쇄할거면 arr[curStation][1] = arr[[arr[curStation][1]][1]이되야함 다음역의 다음역
                int nextStation = postArr[curStation];
                sb.append(nextStation).append("\n");
                int nextNextStation = postArr[nextStation];
                postArr[curStation] = nextNextStation;
                preArr[nextNextStation] = curStation;
            }
            else if(str.contains("CP")){  //CP일시 이전역 폐쇄 후 그 역 번호 출력
                int beStation = preArr[curStation];
                sb.append(beStation).append("\n");
                int beBeStation = preArr[beStation];
                preArr[curStation] = beBeStation;
                postArr[beBeStation] = curStation;
            }
        }
        System.out.println(sb);
    }
}

 

 

 

 

문제 출처

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