[Python] 23309번 철도 공사

 

 

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

23309번: 철도 공사

---

 

24/02/13

 

 

파이썬으로 해결하기 정말 힘든 문제로, C++을 사용할 수 있는 사람이라면 웬만해서는 C++로 해결하기를 권장하는 문제다.

 

주어진 그대로 잘 구현을 했음에도 불구하고 여러 기술들을 활용해야만 시간 초과를 면할 수 있다.

 

Python3로는 통과한 사람이 없는 것으로 보아, Pypy를 사용해야만 풀 수 있는 문제로 보인다. 

---

 

문제 접근 방식:

 

 

문제에서 요구하는 바는 꽤나 명확하다.

 

연결 리스트를 구현하는 문제로, 나의 첫 번째 구현의 경우, None으로 채워진 빈 리스트를 활용했다.

 

빈 리스트의 인덱스는 역의 고유 번호를 나타내고, 그 리스트에 저장되는 값은 하나의 튜플로, 그 역의 이전 역과 다음 역을 저장하는 튜플이다.

 

출력하는 방법은 출력되는 명령이 호출 될 때마다 출력하도록 했다.

 

결과는 시간 초과였다.

 

기본적으로 C++로 구현했더라면 이미 맞았습니다를 받을 수 있었던 문제라고 생각이 되어, 질문 게시판의 여러 코드들을 참고하여 시간을 줄이려고 노력해 보았다.

 

처음으로 시도한 방법은 Chat GPT를 사용해 기존 코드를 C++코드로 변환해 제출한 것이었다.

 

결과는 컴파일 에러, 혹은 시간 초과로, GPT를 이용한 코드 변환은 아직 PS단계에서 미숙하다는 점을 다시 여실히 느꼈다.(물론 내가 잘못 사용한 것일 수도 있다.)

 

두 번째로 시도한 방법은 기존 코드를 main함수에 넣고 main함수를 실행시키는 방법이었다. 두 번째 방법도 시간 초과가 났다.

 

세 번째로 시도한 방법은 기존 코드를 조금 변형하여, 출력하는 내용을 하나의 리스트에 모두 저장해 두었다가 한꺼번에 출력하는 방법이었다.

 

기존 print함수를 여러 번 호출하는 것보다 한 번 호출하는 것이 더 낫다고 생각했고, 그래도 시간초과가 났다.

 

네 번째로 시도한 방법은 기존 코드를 전부 갈아엎고, 두 개의 리스트를 활용하는 방법을 채택했다.

 

기존 코드는 하나의 리스트에 두 개의 역 정보를 튜플로 저장했는데, 새로운 코드는 이전 역을 저장하는 리스트와 다음 역을 저장하는 리스트를 분리하여 구현했다.

 

이 과정에서 기존 역을 제거하거나 새로운 역을 추가하는 함수를 새롭게 구현했다.

 

그래도 시간 초과가 났다.

 

다섯 번째로 시도한 방법은 그 코드에서 None 대신에 0을 넣었다.

 

그랬더니 84%까지 올라가더니 시간 초과가 났다.

 

여섯 번째로 시도한 방법은 if __name__ == '__main__':을 추가해 주었다.

 

그랬더니 Pypy에서 맞았습니다를 받을 수 있었다.

 

시간 초과를 면할 수 있었던 결정적 요인은 세 번째, 네 번째, 다섯 번째, 여섯 번째 방법이었던 것 같다.

 

추가적으로, Pypy에서의 빠른 입출력을 활용하면 1000ms대로 시간을 더욱 줄일 수 있다.

 

다음과 같은 코드를 추가해 주고, ans를 다음과 같이 출력해 주면 된다.

 

import os, io, __pypy__
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ans = __pypy__.builders.StringBuilder()

os.write(1, ans.build().encode())

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 23309번 철도 공사
# 구현, 연결리스트
'''
접근 방법:
인덱스 = 역의 고유 번호
거기에 저장된 값 = (이전역, 다음역)
'''
import sys
import os, io, __pypy__
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ans = __pypy__.builders.StringBuilder()

def main():
    N, M = map(int, input().split())
    station_list = list(map(int, input().split()))

    prv = [0 for _ in range(1_000_000+1)]
    nxt = [0 for _ in range(1_000_000+1)]

    for i in range(N):
        now_station_num = station_list[i]
        prv[now_station_num] = station_list[i-1]
        nxt[now_station_num] = station_list[(i+1)%N]

    # A > B > C to A > B > D > C
    def insert(B, D):
        C = nxt[B]
        nxt[B] = D
        prv[D], nxt[D] = B, C
        prv[C] = D

    # A > B > C to A > C
    def remove(B):
        A, C = prv[B], nxt[B]
        nxt[A], prv[C] = C, A

    for _ in range(M):
        information = input().split()
        command = information[0]
        if command == b'BN':
            i, j = int(information[1]), int(information[2])
            ans.append(str(nxt[i]) + '\n')
            insert(i, j)
        elif command == b'BP':
            i, j = int(information[1]), int(information[2])
            ans.append(str(prv[i]) + '\n')
            insert(prv[i], j)
        elif command == b'CN':
            i = int(information[1])
            ans.append(str(nxt[i]) + '\n')
            remove(nxt[i])
        else:
            i = int(information[1])
            ans.append(str(prv[i]) + '\n')
            remove(prv[i])

    os.write(1, ans.build().encode())
    
if __name__ == '__main__':
    main()