[BOJ] 23309 철도 공사

23309번: 철도 공사

문제

 

연세대학교가 위치한 신촌역이 속한 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개 이상일 때만 들어오며, 이미 설립된 역은 또 설립될 수 없지만 폐쇄된 역은 다시 설립될 수 있다.

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

출력

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

2
7
11
6

---

문제를 보자마자 원형 리스트를 사용하면 되겠다는 생각이 들었다. 그런데 학교에서 배운 기억은 있지만 구현을 많이 해보지는 않아서 잘될까 싶었지만 밑져야 본전이니 일단 도전했다.

 

C++ STL에 원형 리스트가 있었으면 좋았겠지만 잠깐 검색해보니 없는 것 같았다. 그래서 우선 노드 구조체를 만들었다. 삽입은 single로도 쉽게 할 수 있지만 double로 해야 삭제가 편할 것 같아서 포인터를 두 개 만들었다. 그리고 노드를 new나 malloc을 사용하지 않고 정적 할당을 했다. 문제에서 최대로 들어올 수 있는 노드의 개수가 이미 정해져 있어서 정적 할당도 상관없었다. 이렇게 선언해주면 동적 할당에 비해 더 속도가 빠르다. 삼성 SW 특강을 들으면서 배운 테크닉인데 시간이 주어진 알고리즘 문제를 풀 때에 꽤나 효율적인 방법인 것 같다. 

 

처음엔 원하는 역을 찾기 위해 리스트를 탐색하는 함수를 만들어서 그 주소를 반환했다. 내가 작성한 원형 리스트는 리스트에 head가 끼어있기 때문에 탐색 과정에서 현재 노드가 head인 경우는 예외 처리를 해줬다. 명령이 들어올 때마다 리스트를 탐색하다 보니 시간이 너무 오래 걸렸다. 어떻게 시간을 줄일 수 있을까 고민 끝에 이미 배열이 정적 할당되어 있으니까 역의 고유 번호를 그 배열의 인덱스로 사용하면 될 것 같았다. 조건에 이미 역이 있는 경우엔 입력이 들어오지 않는다고 되어 있어서 따로 처리도 필요 없었다. 이렇게 코드를 수정하니 원하는 역의 포인터를 찾기 위해 O(N)이 걸렸던 시간을 O(1)로 줄일 수 있었다. 

 

후기)

어려운 알고리즘이 있기보다는 자료구조만 잘 짜면 쉽게 해결할 수 있는 문제였다. 백준 문제를 풀 때 링크드 리스트는 잘 사용하지 않았는데 오랜만이다.

 

굳이 링크드 리스트를 사용하지 않고 pair를 사용해서 현재 역 기준으로 이전 역과 다음 역의 고유 번호만 저장해도 충분히 문제를 풀 수 있을 것 같다. 나는 약 1000ms 정도 걸렸는데 아마 pair만 사용하면 지금 이 방법보단 빠르지 않을까 싶다.