전기버스 Python(SW Expert Academy)

난이도 : D3

문제번호 : 4831

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVFCzaqeUDFAWg#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

A도시는 전기버스를 운행하려고 한다. 전기버스는 한번 충전으로 이동할 수 있는 정류장 수가 정해져 있어서, 중간에 충전기가 설치된 정류장을 만들기로 했다. 버스는 0번에서 출발해 종점인 N번 정류장까지 이동하고, 한번 충전으로 최대한 이동할 수 있는 정류장 수 K가 정해져 있다. 충전기가 설치된 M개의 정류장 번호가 주어질 때, 최소한 몇 번의 충전을 해야 종점에 도착할 수 있는지 출력하는 프로그램을 만드시오. 만약 충전기 설치가 잘못되어 종점에 도착할 수 없는 경우는 0을 출력한다. 출발지에는 항상 충전기가 설치되어 있지만 충전횟수에는 포함하지 않는다.

다음은 K = 3, N = 10, M = 5, 충전기가 설치된 정류장이 1, 3, 5, 7, 9인 경우의 예이다.

 

입력

첫 줄에 노선 수 T가 주어진다.  ( 1 ≤ T ≤ 50 ) 각 노선별로 K, N, M이 주어지고, 다음줄에 M개의 정류장 번호가 주어진다. ( 1 ≤ K, N, M ≤ 100

출력

#과 노선번호, 빈칸에 이어 최소 충전횟수 또는 0을 출력한다.

예시

입력	출력
3 3 10 5 1 3 5 7 9 3 10 5 1 3 7 8 9 5 20 5 4 7 9 14 17	#1 3 #2 0 #3 4

---

2. 문제풀이

파이썬 Intermediate 1일차 문제입니다. 전기버스 문제인데 이 문제를 봤을때 프로그래머스 라면공장 문제가 생각나더라구요 그래서 이정도의 수준을 원하지는 않았겠지만 우선순위 큐를 이용하여 문제를 풀어봤습니다. 1. 현재위치에 한번충전으로 이동가능한 만큼 더해줍니다. 2. 지나온 위치에 충전소가 있다면 우선순위 큐에 넣어둡니다. 3. 우선순위 큐에서 데이터를 꺼냈을때 현재위치와 제일 가까운 정류장이 나오므로 그위치로 이동합니다. 만약 그사이에 충전소가 없다면 갈수없다고 판단합니다.

 

---

3. 소스코드

from queue import PriorityQueue
import copy
#D3 4831 전기버스
#우선순위 큐를 이용한 문제풀이
length = int(input())
for l in range(1, length+1):
    # n = 종점 정류장, k = 최대이동거리, m = 충전가능 정류장 
    temp = list(map(int, input().split()))
    #충전할 수 있는 정류장
    ch = list(map(int, input().split()))
    #우선순위 큐를 이용하기 위해 깊은복사
    ch_list = copy.deepcopy(ch)
    #현재 거리와 충전횟수 저장
    current = result = 0
    #충전할수 있는 정류장만큼 반복
    #종착역에 갈때까지 반복
    while current + temp[0] < temp[1]:
        #우선순위 큐를 선언
        pq = PriorityQueue()
        #현재거리에 최대이동거리만큼 더해주기
        current += temp[0]
        #충전가능한 정류장이 남을때까지 반복
        while len(ch_list):
            #현재거리가 충전가능한 정류장을 지나갔다면
            if ch_list[0] <= current:
                #우선순위 큐에 넣어주고 리스트에서 빼기
                pq.put(-ch_list[0])
                ch_list.pop(0)
            #충전가능한 정류장이 없다면 반복문 나가기
            else: break
        #우선순위 큐가비어있다면
        if pq.empty():
            #충전가능한 정류장이 없는것이므로 결과를 0으로 넣어주고 반복문을 나간다
            result = 0
            break
        #위의 조건에 걸리지 않았다면 충전가능한 마지막정류장을 현재거리로 넣어준다.
        current = -pq.get()
        #충전을 했으므로 충전횟수를 증가시킨다
        result += 1
    #결과값을 출력한다.
    print("#{} {}".format(l, result))