야간전술보행 (Python)

문제설명

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/133501

프로그래머스

중요 포인트

1. 화랑이가 이동하면 경비병들이 모두 근무를 선다.(1초에서 함께 시작)
2. 화랑이는 1초에 1m/s로 움직이며 경비병들은 근무와 휴식을 번갈아가며 수행한다.
3. 경비병들의 감시 구간은 겹치지 않는다.
4. 화랑이는 멈추지 않는다.
5. 화랑이가 경비병의 감시 구간을 지나갈 때 근무중이라면 붙잡힌다.
6. 입력되는 경비구간은 [시작, 끝]이 아니다. (끝 부분이 앞으로 올 수도 있다.)

 

출력

화랑이가 이동한 최대 거리를 출력해라.

 

입력

• distance : 화랑이가 이동해야할 거리(Integer)
• scope : 경비병들의 경비 구간(2-array)
• times : 경비병들의 휴식, 근무 시간(2-array)

입력 데이터 (출처 : 프로그래머스)

이 때 scope에 해당하는 index의 times가 해당 경비병의 휴식과 근무 시간이다. 위 예시는 2명의 경비원에 대한 정보를 담고 있다.

 

문제 해결

경비병 근무표와 화랑이의 위치(출처 - 프로그래머스)

화랑이가 이동을 멈추게 되는 경우는 경비에게 붙잡혔을 때와 목표지점에 도달하였을 때이다. 따라서 경비병의 경계 구역을 통과할 때만 고려해주면 문제를 해결할 수 있다. 위 표는 입력예시의 데이터를 활용하여 만든 표이다.

첫 번째 경비병은 3~4초 구간에서 경계를 하고, 두 번째 경비병은 5~8초 구간에서 경계를 한다. 그렇다면 그 구간을 통과할 때 경비병의 상태만 고려하면 문제를 해결할 수 있다.

 

첫 번째 경비병의 경계구역을 통과할 때 3~4초간 모두 휴식이므로 무사히 통과할 수 있다. 하지만 두 번째 경비병의 경비구역을 통과할 때 8초에 경비병이 근무에 투입되므로 붙잡히게 된다. 따라서 최종 결과는 8초가 된다.

 

경비병들의 상태변화는 근무시간 + 휴식시간으로 로테이션 된다. 위치를 1이 아니라 0을 시작지점으로 고려해보면 근무시간 + 휴식시간의 값으로 mod연산을 하면 경비병의 근무 상태가 순환됨 을 알 수 있을 것이다. mod연산을 활용하여 근무자의 경계구역을 지나가는 시간대에 경비병의 근무상태를 구할 수 있고 문제를 해결할 수 있다.

코드

def solution(distance, scope, times):
    for s in scope:
        s.sort()
    zip_list = list(zip(scope, times))
    zip_list.sort(key = lambda x:x[0][0])
    
    for guard in range(len(zip_list)):
        mod = zip_list[guard][1][0] + zip_list[guard][1][1]
        work = zip_list[guard][1][0]
        for time in range(zip_list[guard][0][0]-1, zip_list[guard][0][1]):
            remainder = time % mod
            if remainder - work < 0:
                return time + 1
    return distance