[Python] SW Expert Academy - 4831. 전기버스

SW Expert Academy 4831번 전기버스 문제는 한 번 충전 시 최대 이동할 수 있는 정류장 수 K가 정해져 있을 때, 종점인 N번 정류장까지 최소한 몇 번의 충전을 해야 종점에 도착할 수 있는지를 출력하는 문제이다. 난이도는 D3이고, 리스트 자료구조에 관한 문제이다.

 

SW Expert Academy 4831번 전기버스 문제 정보

자료구조 분류

- 리스트

난이도

- D3

 

전기버스 문제 요약

• 버스는 0번 정류장에서 출발해 종점인 N번 정류장까지 이동한다. 0번 정류장에는 항상 충전기가 있지만 충전 횟수에는 포함하지 않는다.
• 한번 충전으로 최대 이동할 수 있는 정류장 수 K가 정해져 있다.
• 충전기가 설치된 M개의 정류장 번호가 주어진다.
• 각 노선별로 K, N, M, M개의 정류장 번호가 주어진다. ( 1 ≤ K, N, M ≤ 100 )
• 종점까지 도착하기 위한 최소한의 충전 횟수를 구한다. (충전기 설치가 잘못되어 종점에 도착할 수 없는 경우는 0을 출력한다.)

문제 풀이 과정

• 정류장 번호는 index, 충전기가 설치된 정류장의 값은 1, 미설치된 정류장의 값은 0인 정류장 정보를 담은 station 리스트를 정의하였다.
• 남은 이동 횟수가 0 초과이고 현재 정류장이 종점이 아닐 동안 탐색한다.
• 최대 이동 가능한 정류장 수 K만큼 현재 정류장 위치를 미리 이동시켜놓고 이전 정류장으로 한 칸씩 이동하며 충전기가 있는 정류장을 만날 때까지 탐색한다.
• 충전기가 있는 정류장을 만나면 충전 횟수를 1 증가, 남은 이동 횟수를 K로 초기화, 현재 정류장 위치를 K 만큼 앞으로 이동시킨다(이때, 종점을 만나면 탐색이 끝난다.).
• 종점에 도착하기 전에 이동 가능 횟수가 0이 되면 충전 횟수가 0으로 리셋된다.
• 테스트 케이스 번호, 충전 횟수를 출력한다.

코드

• station [] - 정류장 정보를 담은 리스트 (index: 정류장 번호, value=1: 충전기가 설치된 정류장, value=0: 미설치된 정류장)
• chargeCnt - 충전 횟수
• remainMove - 남은 이동 횟수
• nowPos - 현재 정류장 위치

T = int(input())
for i in range(T):
    K, N, M = map(int, input().split())
    station = [0 for i in range(N+1)]
    chargerNum = list(map(int, input().split()))
    
    for cn in chargerNum:
        station[cn] += 1
        
    chargeCnt = 0
    remainMove = K
    nowPos = K
    
    while remainMove > 0 and nowPos != N:
        if station[nowPos] == 1:
            chargeCnt += 1
            remainMove = K
            if nowPos + K <= N:
                nowPos += K
            else:
                nowPos = N
        else:
            nowPos -= 1
            remainMove -= 1
            
    if nowPos != N:
        chargeCnt=0
        
    print("#{0} {1}".format(i+1, chargeCnt))

 

틀린 문제 풀이 과정

1. 정류장 한 칸씩 전진하면서 충전기가 있는 정류장을 만났을 때
2. 이동한 거리가 K보다 작으면 현재 정류장을 tmp에 저장해 놓고 다음 충전기가 설치된 정류장을 탐색 (1번으로)
3. K와 같을 때 충전하고, tmp 리셋
4. K보다 클 때
   4-1. tmp에 정류장이 있으면 tmp 정류장에서 충전 후 tmp에 현재 정류장 저장
   4-2. tmp에 정류장이 없으면 충전 횟수 0으로 리셋되고 종료
5. 2~4번의 과정을 전체 정류장을 탐색할 때까지 반복

10개의 테스트 케이스 중 2개가 fail이 났는데 지금 보니 충전기 정류장을 건너뛸 때 1개의 정류장 건너뛰는 것만 생각하고 2개 이상의 충전기 정류장을 건너뛸 때는 고려하지 않아서 fail이 난 듯하다.

---

SW Expert Academy 4831번 전기버스 문제는 리스트 자료구조에 관한 문제이며 언어는 파이썬을 사용하였다. 난이도는 D3 여서 그런지 해결법을 생각하는 데에 시간이 많이 걸렸고 코드 제출 결과 fail도 났었다. 결국은 다른 사람의 해결책을 참고하여 성공은 했지만 다음부터는 혼자 힘으로 더 풀어봐야겠다.