[정글 알고리즘] - [중] - 백준 23309-연결 리스트 - 철도 공사 (백준 플래티넘4)

 고민하다 "원형 연결 리스트인데, 포인터를 배열로 구현하면 O(1)"이라는 걸 잡았다. 삽입·삭제마다 배열을 통째로 밀거나 탐색하면 절대 안 되고, prev[x], next[x] 두 배열만 수정하는 방식이 핵심이다.

📋 문제 소개

항목	내용
문제 번호	백준 23309
난이도	플래티넘 4
분류	자료구조, 연결 리스트 (원형 이중 연결 리스트)
핵심 자료구조	prev_station[], next_station[] 배열 (역 번호를 인덱스로 사용)
N, M 범위	N ≤ 500,000 / M ≤ 1,500,000 / 역 번호 ≤ 1,000,000
시간 제한	1초

명령	동작
BN i j	i의 다음 역 번호 출력 → i와 그 다음 역 사이에 j 설립
BP i j	i의 이전 역 번호 출력 → i와 그 이전 역 사이에 j 설립
CN i	i의 다음 역 폐쇄 → 그 역 번호 출력
CP i	i의 이전 역 폐쇄 → 그 역 번호 출력

입력 예시	출력 예시
4 5 1 3 5 7 BN 1 2 BP 5 4 CN 2 CP 7 BN 7 6	3 3 3 5 1

❌ 리스트 직접 탐색 — 왜 안 되는가

역 목록을 파이썬 리스트로 관리하고 중간 삽입/삭제를 하면 어떻게 될까?

# 절대 안 되는 방식
stations = [1, 3, 5, 7]

# i의 인덱스를 찾아서 삽입 → O(N)
idx = stations.index(i)         # 탐색 O(N)
stations.insert(idx + 1, j)     # 삽입 O(N)

방식	탐색	삽입/삭제	명령 1회	M=1,500,000 전체	판정
리스트 탐색	O(N)	O(N)	O(N)	O(N×M) ≈ 7.5×10¹¹	❌ 시간 초과
배열 포인터	O(1)	O(1)	O(1)	O(N + M) ≈ 2×10⁶	✅ 통과

핵심 발상: 역 번호가 최대 1,000,000이므로 prev_station[x], next_station[x] 배열을 크기 1,000,001로 만들고, 역 번호를 인덱스로 직접 사용하면 탐색 없이 O(1)로 이웃 역을 바로 알 수 있다.

🔗 원형 이중 연결 리스트 구조

초기 상태: 역 1 → 3 → 5 → 7 → (다시 1)

↙ (7에서)				(7으로) ↘
1	⇌	3	⇌	5	⇌	7

⇌ = 양방향 연결 (next/prev 모두 존재) | 7의 next = 1, 1의 prev = 7

역 x	prev_station[x]	next_station[x]
1	7 (마지막 역)	3
3	1	5
5	3	7
7	5	1 (첫 번째 역)

🛠️ 초기화 코드 이해

MAX = 1000000 + 1
prev_station = [0] * MAX
next_station = [0] * MAX

for i in range(n):
    now = stations[i]
    prev_station[now] = stations[i - 1]       # (A)
    next_station[now] = stations[(i + 1) % n] # (B)

라인	설명	i=0 (역 1) 예시	i=3 (역 7) 예시
(A)	stations[i-1] i=0일 때 i-1=-1 → 파이썬에서 자동으로 마지막 원소	prev[1] = stations[-1] = 7	prev[7] = stations[2] = 5
(B)	(i+1) % n 마지막 역(i=n-1)의 다음은 인덱스 0 (첫 번째 역)	next[1] = stations[1] = 3	next[7] = stations[0] = 1

파이썬 음수 인덱스 활용: stations[-1]은 리스트의 마지막 원소다. 그래서 i=0일 때 stations[i-1] = stations[-1]이 자동으로 마지막 역을 가리켜 원형 연결이 완성된다.

🔵 BN i j — 다음 역 출력 후 사이에 삽입

예시: BN 1 2 → 역 1의 다음 역(3) 출력, 1과 3 사이에 역 2 삽입

Before:

1

⇌

3 (nxt)

⇌

5

After:

1

⇌

2 (신규)

⇌

3

⇌

5

순서	코드	의미	변경 전	변경 후
0	nxt = next_station[1]	기존 다음 역 저장 (덮어쓰기 전에 백업)	—	nxt = 3
1	next_station[1] = 2	1의 다음을 j(2)로 변경	next[1] = 3	next[1] = 2
2	prev_station[2] = 1	j(2)의 이전을 i(1)로 설정	prev[2] = 0 (없음)	prev[2] = 1
3	next_station[2] = nxt	j(2)의 다음을 nxt(3)로 설정	next[2] = 0 (없음)	next[2] = 3
4	prev_station[nxt] = 2	nxt(3)의 이전을 j(2)로 변경	prev[3] = 1	prev[3] = 2

순서가 중요하다: nxt = next_station[i]를 먼저 백업해두지 않으면, next_station[i] = j로 덮어쓴 뒤에는 원래 다음 역을 알 수 없다.

🟣 BP i j — 이전 역 출력 후 사이에 삽입

예시: BP 5 4 → 역 5의 이전 역(3) 출력, 3과 5 사이에 역 4 삽입

Before:

1

⇌

2

⇌

3 (prv)

⇌

5 (i)

After:

1

⇌

2

⇌

3

⇌

4 (신규)

⇌

5

순서	코드	의미
0	prv = prev_station[5] → prv = 3	기존 이전 역 백업
1	next_station[3] = 4	prv(3)의 다음을 j(4)로 변경
2	prev_station[4] = 3	j(4)의 이전을 prv(3)로 설정
3	next_station[4] = 5	j(4)의 다음을 i(5)로 설정
4	prev_station[5] = 4	i(5)의 이전을 j(4)로 변경

🔴 CN i — 다음 역 삭제

현재 상태: 1 ⇌ 2 ⇌ 3 ⇌ 4 ⇌ 5 ⇌ 7 ⇌ (1)
예시: CN 2 → 역 2의 다음 역(3) 삭제, 3 출력

Before:

2 (i)

⇌

3 (삭제)

⇌

4 (new_next)

After:

2

⇌

4

순서	코드	의미
0	target = next_station[2] → target = 3	삭제할 역 = i의 다음 역
1	new_next = next_station[3] → new_next = 4	target 다음 역 백업
2	next_station[2] = 4	i(2)의 다음을 new_next(4)로 연결 → target(3) 건너뜀
3	prev_station[4] = 2	new_next(4)의 이전을 i(2)로 변경 → target(3) 완전 제거

🟠 CP i — 이전 역 삭제

예시: CP 7 → 역 7의 이전 역(5) 삭제, 5 출력

Before:

4 (new_prev)

⇌

5 (삭제)

⇌

7 (i)

After:

4

⇌

7

순서	코드	의미
0	target = prev_station[7] → target = 5	삭제할 역 = i의 이전 역
1	new_prev = prev_station[5] → new_prev = 4	target의 이전 역 백업
2	prev_station[7] = 4	i(7)의 이전을 new_prev(4)로 → target(5) 건너뜀
3	next_station[4] = 7	new_prev(4)의 다음을 i(7)로 → target(5) 완전 제거

📊 4가지 명령 포인터 변경 비교

명령	출력	변경 전 구조	변경 후 구조	수정되는 포인터
BN i j	next[i]	i ⇌ nxt	i ⇌ j ⇌ nxt	next[i], prev[j], next[j], prev[nxt]
BP i j	prev[i]	prv ⇌ i	prv ⇌ j ⇌ i	next[prv], prev[j], next[j], prev[i]
CN i	next[i]	i ⇌ target ⇌ nn	i ⇌ nn	next[i], prev[nn]
CP i	prev[i]	np ⇌ target ⇌ i	np ⇌ i	prev[i], next[np]

패턴 정리: 삽입은 포인터 4개 수정, 삭제는 포인터 2개 수정. 항상 수정 전에 덮어쓸 값을 먼저 변수에 저장해두는 것이 핵심이다.

🔬 입출력 예제 전체 시뮬레이션

초기: 1 ⇌ 3 ⇌ 5 ⇌ 7 ⇌ (1)

#	명령	출력	처리 후 노선 상태	변경 내용
0	초기	—	1 ⇌ 3 ⇌ 5 ⇌ 7 ⇌ (1)	—
1	BN 1 2	3	1 ⇌ 2 ⇌ 3 ⇌ 5 ⇌ 7 ⇌ (1)	1과 3 사이에 2 삽입
2	BP 5 4	3	1 ⇌ 2 ⇌ 3 ⇌ 4 ⇌ 5 ⇌ 7 ⇌ (1)	3과 5 사이에 4 삽입 (5 기준 이전)
3	CN 2	3	1 ⇌ 2 ⇌ 3 ⇌ 4 ⇌ 5 ⇌ 7 ⇌ (1) → 1 ⇌ 2 ⇌ 4 ⇌ 5 ⇌ 7 ⇌ (1)	2의 다음 역(3) 삭제
4	CP 7	5	1 ⇌ 2 ⇌ 4 ⇌ 5 ⇌ 7 ⇌ (1) → 1 ⇌ 2 ⇌ 4 ⇌ 7 ⇌ (1)	7의 이전 역(5) 삭제
5	BN 7 6	1	1 ⇌ 2 ⇌ 4 ⇌ 7 ⇌ 6 ⇌ (1)	7과 1 사이에 6 삽입 (원형!)

✅ 최종 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
stations = list(map(int, input().split()))

MAX = 1000000 + 1
prev_station = [0] * MAX
next_station = [0] * MAX

# 초기 원형 연결 설정
for i in range(n):
    now = stations[i]
    prev_station[now] = stations[i - 1]       # i=0이면 stations[-1] = 마지막 역
    next_station[now] = stations[(i + 1) % n] # 마지막 역의 next = 첫 번째 역

answer = []

for _ in range(m):
    cmd = input().split()

    if cmd[0] == 'BN':
        i, j = int(cmd[1]), int(cmd[2])
        nxt = next_station[i]        # 기존 다음 역 백업
        answer.append(str(nxt))      # 출력

        next_station[i]   = j        # i → j
        prev_station[j]   = i        # j ← i
        next_station[j]   = nxt      # j → nxt
        prev_station[nxt] = j        # nxt ← j

    elif cmd[0] == 'BP':
        i, j = int(cmd[1]), int(cmd[2])
        prv = prev_station[i]        # 기존 이전 역 백업
        answer.append(str(prv))      # 출력

        next_station[prv] = j        # prv → j
        prev_station[j]   = prv      # j ← prv
        next_station[j]   = i        # j → i
        prev_station[i]   = j        # i ← j

    elif cmd[0] == 'CN':
        i = int(cmd[1])
        target   = next_station[i]          # 삭제 대상
        new_next = next_station[target]     # 그 다음 역 백업
        answer.append(str(target))          # 출력

        next_station[i]        = new_next   # i → new_next (target 건너뜀)
        prev_station[new_next] = i          # new_next ← i

    elif cmd[0] == 'CP':
        i = int(cmd[1])
        target   = prev_station[i]          # 삭제 대상
        new_prev = prev_station[target]     # 그 이전 역 백업
        answer.append(str(target))          # 출력

        prev_station[i]        = new_prev   # i ← new_prev (target 건너뜀)
        next_station[new_prev] = i          # new_prev → i

print('\n'.join(answer))

⏱️ 시간 복잡도

단계	작업	복잡도
초기화	N개 역 prev/next 설정	O(N)
명령 처리	각 명령 포인터 최대 4개 수정	O(1) × M = O(M)
전체	N=500,000, M=1,500,000 → ≈ 2,000,000 연산	O(N + M) ✅

💬 마무리

역 번호를 인덱스로 쓰는 배열 2개(prev[], next[])로 원형 이중 연결 리스트를 구현하는 것이 핵심이다. 삽입은 포인터 4개, 삭제는 포인터 2개만 바꾸면 O(1)에 끝난다.

리스트를 직접 탐색하면 O(N×M)로 절대 통과 못 한다. 이 문제는 자료구조 선택이 곧 합/불합을 결정한다.