[#1263] 시간 관리

문제

#1263 시간 관리
Gold5
적용 알고리즘: 정렬 알고리즘

---

풀이 방법

• 진영이가 가장 미룰 수 있는 시간은 일 중에서 종료시간이 가장 늦은 일의 시간이다. 이를 최대 시간으로 잡고 시작한다.
• 입력된 배열을 종료시간을 기준으로 내림차순으로 정렬한다.(이때 람다 함수를 사용하여 차원을 지정하여 정렬할 수 있다.)
• 종료시점이 가장 늦은 일을 최대한 뒤로 미루어야 한다.

코드 흐름

1. 입력받은 배열을 종료시간을 기준으로 내림차순으로 정렬한다.
2. 종료시간이 가장 긴 시간을 최대 시간(time)으로 잡는다.(정렬된 배열에서 load[0][1] 항목)
3. time에서 일이 걸리는 시간을 뺀다. 만일 뺀 시간이 그 다음(idx + 1) 종료시점보다 큰 경우, 일을 그 전에 끝내야 하므로 그 다음 종료시점이 늦은 시간을 time으로 설정한다.
4. 만일 3의 과정에서 뺀 시간이 그 다음(idx + 1) 종료시점보다 작은 경우, 일을 바로 시작해도 되므로 뺀 시간이 현재시간이 된다.
5. 3, 4의 과정을 time이 0 이상이거나 인덱스 변수가 입력한 변수보다 작을 경우 반복한다.
6. 루프에 나와서 time의 값이 0 이상인 경우 일을 완료할 수 있다는 의미이므로 time값을 출력하고, 음수인 경우 일을 제 시간내에 다 끝낼 수 없다는 의미이므로 -1을 출력한다.

코드

n = int(input())

load = []
temp = []
for i in range(n):
    temp = [int(m) for m in input().split()]
    load.append(temp)

load.sort(key=lambda x: (-x[1], -x[0]))     # 각 요소의 두 번째 인덱스를 기준으로 정렬

time = load[0][1]       # 정렬완료. 가장 늦은 종료시점이 시작점이 됨
temp = 0
idx = 0
while(time > 0 and idx < n):
    temp = time - load[idx][0]
    if (idx == n - 1):
        time = temp
        break
    elif (temp > load[idx + 1][1]):
        time = load[idx + 1][1]
    else:
        time = temp
    idx += 1

if (time >= 0):
    print(time)
else:
    print(-1)

체감 난이도: 2.5/5
Gold5 치고는 무난무난한 문제였다. 만일 종료시간이 같은 일인데 일의 소요 시간이 다른 경우는 어떻게 정렬을 해야하는지 고민했었는데, 생각해보니 이 경우는 다른 처리를 하지 않아도 될 것 같다. 어떤 일을 먼저 하든 둘 합의 소요시간은 똑같기 때문이다. 아 참고로 문제의 주인공 이름과 오빠 이름이 동일하다.

---

[파이썬 구문]

특정 인덱스를 기준으로 정렬
lambda 함수를 사용하여 2차원 이상의 매배열을 특정 인덱스를 기준으로 정렬할 수 있다. 부호 ‘-‘는 내림차순을 의미한다.

# 1번쨰 인덱스로 우선 내림차순 정렬 후 동일한 원소에 대해서 0번째 인덱스로 오름차순 정렬
load.sort(key=lambda x: (-x[1], x[0]))