[SWEA]4831. 파이썬 SW문제해결 기본 - LIST 1 : 전기버스

---

파이썬 SW문제해결 기본 - LIST 1

4831. 07 전기버스(SW문제)

---

이미지를 클릭하시면 SW Expert Academy의 해당 강좌로 이동합니다

06. 전기버스

🎲문제 : 위 이미지를 클릭하여 SWEA 이동 -> 7차시 1일차 - 전기버스

---

🥾문제 접근:

- 현재 위치에서 이동 가능한 거리(K) 이내의 충전 가능한 정류장(M)으로 이동한다. 종점(N)에 도달할 때 까지 이를 반복하며 충전 횟수를 카운팅한다. 만일 이동 가능한 거리(K) 이내의 충전 가능한 정류장이 없다면 종점에 도착할 수 없다고 판단한다.

- 현재 상황에서 가능한 경우의 수 가운데 최선의 선택을 하며 진행하는 알고리즘이다. 즉 이전에 배운 "Greedy Algorithm"에 해당한다.

Greedy Algorithm란? - [SWEA]파이썬 SW문제해결 기본 - LIST 1 : Greedy Algorithm

[SWEA]파이썬 SW문제해결 기본 - LIST 1 : Greedy Algorithm

---

🎯 문제 해결:
📍 시도한 순서대로 정리되어 있으며 마지막 코드가 최종 코드이다.

---

첫 번째 시도

T = int(input())
for test_case in range(1, T + 1):
    #K: 이동 가능한 거리, N: 종점, M: 충전소 개수
    K, N, M = map(int, input().split(" "))
    #stations: 충전 가능 정류장 정보
    stations= list(map(int, input().split(" ")))
    
    #1
    now = 0
    can_go = now+K
    charge_station = 0
    count = 0
    
    #2
    while (can_go<N):
        #3
        for i in stations:
            if now < i <= can_go:
                charge_station = i
            elif can_go < i:
                break
        #4
        if charge_station == -1:
            count = 0
            break
        #5
        now = charge_station
        can_go = now+K
        count += 1
        charge_station = -1
        
    print(f"#{test_case} {count}")

#1 각 케이스 별로 필요한 변수를 초기화했다. 

📦 now: 현재 위치
📦 can_go: 최대 이동 가능 거리(현재 위치 + 이동 가능한 거리) #내가 봐도 변수 작명 센스가 구리다
📦 station: 다음 충전소 위치
📦 count: 충전 횟수를 세기 위한 변수

#2 최대 이동 가능 거리(can_go)가 목적지(N)에 도달하기 전까지 반복한다.

#3 충전 가능 정류장(stations) 중 다음으로 이동할 충전소를 탐색 후 다음 충전소 위치(charge_station)에 저장한다.

충전소가 현재 위치(now)와 최대 이동 가능 거리(can_go) 사이에 있다면 다음 충전소 위치(charge_station)에 저장하고, 같은 조건에서 더욱 멀리 갈 수 있는 충전소가 있다면 다음 충전소 위치(charge_station)를 갱신한다. 

만약 충전소가 최대 이동 가능 거리(can_go)보다 멀리 있다면, 반복을 중단한다. (반복을 중단하지 않아도 코드는 정상적인 결과를 출력할 것이다. 그러나 덜 효율적일 것이다.)

#4 최대 이동 가능 거리(can_go) 이내에 이동 가능한 충전소가 없을 경우 반복을 중단하고 이동 불가(count=0)을 하는 코드이다. 조건식이 charge_station==-1인 이유는 다음 "#5"에서 나온다.

#5 현재 위치(now)를 다음 충전소 위치(charge_station)로 이동한다. 그 후 최대 이동 가능 거리(can_go)를 업데이트 한다. 충전소 이동이 수행됐으므로, count를 1 증가시킨다.

그리고 충전소에 도달하지 못할 경우를 대비하여 다음 충전소 위치(charge_station)에 -1을 대입한다. 만약 다음 반복 중 "#3"에서 충전소 위치를 찾지 못한다면 다음 충전소 위치(charge_station)가 업데이트되지 않을 것이다. 따라서 다음 충전소 위치(charge_station)가 -1이므로 "#4"에서 목적지 도달 불가능 판단을 하게 된다.

이 코드의 결과는? - ✅PASS / 실행 시간 : 0.12304s

---

두 번째 시도

첫 번째 코드의 통과로 그대로 마칠 수도 있다. 그러나 현재 충전소 위치에 대한 인덱스를 저장해둔다면 조금 더 효율적으로 충전소를 탐색할 가능성이 있다. 전체적인 알고리즘 흐름은 위와 같지만 인덱스를 추가하였다.

T = int(input())
for test_case in range(1, T + 1):
    #K: 이동 가능한 거리, N: 종점, M: 충전소 개수
    K, N, M = map(int, input().split(" "))
    #stations: 충전 가능 정류장 정보
    stations= tuple(map(int, input().split(" ")))
    
    now = 0
    can_go = now+K
    charge_station = -1
    count = 0
    index = 0
    
    while (can_go<N):
        for i in range(index, M):
            if stations[i] <= can_go:
                charge_station = stations[i]
            else:
                index = i
                break
        if charge_station == -1:
            count = 0
            break
        now = charge_station
        can_go = now+K
        count += 1
        charge_station = -1
        
    print(f"#{test_case} {count}")

이 코드의 결과는? - ✅PASS / 실행 시간 : 0.12680s

---

최종 시도

인덱스를 저장하여 반복 횟수를 줄이고자 했으나 오히려 실행 시간이 늘어났다. 줄어든 반복 횟수의 수행 속도보다 현재 위치를 인덱스에 저장하며 늘어난 수행 속도가 더 큰 듯하다. 따라서 이 부분은 다시 이전으로 돌렸다. 다만 stations가 변경되지 않는 점에 착안하여 list->tuple로 변경하였다.

T = int(input())
for test_case in range(1, T + 1):
    #K: 이동 가능한 거리, N: 종점, M: 충전소 개수
    K, N, M = map(int, input().split(" "))
    #stations: 충전 가능 정류장 정보
    stations= tuple(map(int, input().split(" ")))
    

    now = 0
    can_go = now+K
    charge_station = 0
    count = 0
    
    while (can_go<N):
        for i in stations:
            if now < i <= can_go:
                charge_station = i
            elif can_go < i:
                break

        if charge_station == -1:
            count = 0
            break

        now = charge_station
        can_go = now+K
        count += 1
        charge_station = -1
        
    print(f"#{test_case} {count}")

이 코드의 결과는? - ✅PASS / 실행 시간 : 0.12264s