[코드잇] 알고리즘 연습 level 1 03 빠르게 산 오르기 python

빠르게 산 오르기.py

실습과제
신입 사원 장그래는 마부장님을 따라 등산을 가게 되었습니다.


탈수를 방지하기 위해서 1km당 1L의 물을 반드시 마셔야 하는데요. 다행히 등산길 곳곳에는 물통을 채울 수 있는 약수터가 마련되어 있습니다. 다만 매번 줄서 기다려야 한다는 번거로움이 있기 때문에, 시간을 아끼기 위해서는 최대한 적은 약수터를 들르고 싶습니다.


함수 select_stops는 파라미터로 약수터 위치 리스트 water_stops와 물통 용량 capacity를 받고, 장그래가 들를 약수터 위치 리스트를 리턴합니다. 앞서 설명한 대로 약수터는 최대한 적게 들러야겠죠.


참고로 모든 위치는 km 단위이고 용량은 L 단위입니다. 그리고 등산하기 전에는 이미 물통이 가득 채워져 있으며, 약수터에 들르면 늘 물통을 가득 채운다고 가정합시다.


예시를 하나 볼게요.


# 약수터 위치: [1km, 4km, 5km, 7km, 11km, 12km, 13km, 16km, 18km, 20km, 22km, 24km, 26km]
# 물통 용량: 4L
select_stops([1, 4, 5, 7, 11, 12, 13, 16, 18, 20, 22, 24, 26], 4)

처음에 4L의 물통이 채워져 있기 때문에, 장그래는 약수터에 들르지 않고 최대 4km 지점까지 올라갈 수 있습니다. 탈수 없이 계속 올라가기 위해서는 1km 지점이나 4km 지점에서 물통을 채워야겠죠?


최대한 적은 약수터를 들르면서 올라가야 하고, 마지막에 산 정상인 26km 지점의 약수터를 들르면 성공적인 등산입니다.


실행 결과

[4, 7, 11, 13, 16, 20, 24, 26]
[5, 8, 12, 17, 23, 28, 32, 38, 44, 47]




정답

def select_stops(water_stops, capacity):
    # 코드를 작성하세요.
    answer =[]
    target = 0
    startindex =0
    while target != water_stops[len(water_stops)-1]: # 마지막 약수터에 도달하기까지 계속 루틴반복
        xx=0
        for i in range(startindex,len(water_stops)): #현재 위치에서 끝까지 루틴 시작
            xx =i
            if target+capacity < water_stops[i]: # 용량초과한만큼 움직엿다면 이전 위치에서 가장 큰 값을 정답에 저장
                answer.append(max(water_stops[:i]))
                target=answer[len(answer) - 1]
                startindex = i-1                #현재 위치 저장
                break

        if xx == len(water_stops)-1:
            answer.append(water_stops[len(water_stops)-1])
            break




    return answer


# 테스트
list1 = [1, 4, 5, 7, 11, 12, 13, 16, 18, 20, 22, 24, 26]
print(select_stops(list1, 4))

list2 = [5, 8, 12, 17, 20, 22, 23, 24, 28, 32, 38, 42, 44, 47]
print(select_stops(list2, 6))


###코드잇 풀이
##일단 시간복잡도가 O(n)밖에 안됨 반복문이 하나밖에 쓰이지 않음
##나도 할려고 했는데 capacity를 잘못 생각해서 복잡하게 푼듯..

# i 지점 까지 갈수없다고 체크하는 부분이 중요한 문제였다
def select_stops(water_stops, capacity):
    # 약수터 위치 리스트
    stop_list = []

    # 마지막 들른 약수터 위치
    prev_stop = 0

    for i in range(len(water_stops)):
        # i 지점까지 갈 수 없으면, i - 1 지점 약수터를 들른다
        if water_stops[i] - prev_stop > capacity:
            stop_list.append(water_stops[i - 1])
            prev_stop = water_stops[i - 1]

    # 마지막 약수터는 무조건 간다
    stop_list.append(water_stops[-1])

    return stop_list


# 테스트
list1 = [1, 4, 5, 7, 11, 12, 13, 16, 18, 20, 22, 24, 26]
print(select_stops(list1, 4))

list2 = [5, 8, 12, 17, 20, 22, 23, 24, 28, 32, 38, 42, 44, 47]
print(select_stops(list2, 6))