danbibibi
article thumbnail

1. 문제

문제 바로가기> BOJ 23309번: 철도 공사

 

23309번: 철도 공사

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

www.acmicpc.net

 

 

2. 풀이

이중 연결 리스트 개념을 이용하되, 

각 원소에 접근할 때 O(1)로 접근하기 위해 이전 역(prev)과 다음 역(next)을 가지는 벡터를 만들어 주었다. 

그렇지 않고, 해당 역을 찾기 위해 또다시 탐색을 진행해야 한다면, 시간 초과가 발생하기 때문!! O(N*M),,,

 

<cpp />
#include <iostream> #include <vector> #define MAX 1000001 using namespace std; struct INFO { int prev; int next; }; int N, M; vector<INFO> station(MAX); void input() { cin >> N >> M; int prev, start, end; cin >> start; prev = start; int num; for (int i = 1; i < N - 1; i++) { cin >> num; station[prev].next = num; station[num].prev = prev; prev = num; } cin >> end; station[prev].next = end; station[end].prev = prev; station[end].next = start; station[start].prev = end; } void BN(int i, int j) { cout << station[i].next << "\n"; // 고유 번호 i를 가진 역의 다음 역의 고유 번호 if (station[j].prev != 0) // 이미 설립된 역 return; // 그 사이에 고유 번호 j인 역을 설립 station[j].prev = i; station[j].next = station[i].next; station[station[i].next].prev = j; station[i].next = j; } void BP(int i, int j) { cout << station[i].prev << "\n"; // 고유 번호 i를 가진 역의 이전 역의 고유 번호 if (station[j].prev != 0) // 이미 설립된 역 return; // 그 사이에 고유 번호 j인 역을 설립 station[j].prev = station[i].prev; station[j].next = i; station[station[i].prev].next = j; station[i].prev = j; } void CN(int i) { int deleted = station[i].next; cout << deleted << "\n"; // 고유 번호 i를 가진 역의 다음 역의 고유 번호 // 고유 번호 i를 가진 역의 다음 역 폐쇄 station[i].next = station[station[i].next].next; station[station[i].next].prev = i; station[deleted] = {0, 0}; } void CP(int i) { int deleted = station[i].prev; cout << deleted << "\n"; // 고유 번호 i를 가진 역의 이전 역의 고유 번호 // 고유 번호 i를 가진 역의 이전 역 폐쇄 station[i].prev = station[station[i].prev].prev; station[station[i].prev].next = i; station[deleted] = {0, 0}; } void solution() { int i, j; string cmd; while (M--) { cin >> cmd; if (cmd == "BN") { cin >> i >> j; BN(i, j); } else if (cmd == "BP") { cin >> i >> j; BP(i, j); } else if (cmd == "CN") { cin >> i; CN(i); } else if (cmd == "CP") { cin >> i; CP(i); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); input(); solution(); }

 

'문제 풀이 > 백준' 카테고리의 다른 글

BOJ 1766번: 문제집  (0) 2023.03.23
BOJ 1726번: 로봇  (0) 2023.03.23
BOJ 12852번: 1로 만들기 2  (0) 2023.03.21
BOJ 2623번: 음악프로그램  (0) 2023.03.21
BOJ 1584번: 게임  (0) 2023.03.18
profile

danbibibi

@danbibibi

꿈을 꾸는 시간은 멈춰 있는 것이 아냐 두려워하지 마 멈추지 마 푸른 꿈속으로