Greedy Algorithm - 컴퓨터 배정

문제

컴퓨터를 쓸 학생 수, 각각의 학생이 컴퓨터를 쓰는 시간을 [시작 시간, 종료 시간]을 순서대로 배열에 받아온다.
# 학생 수 = 5 times = [[1, 4], [2, 3], [5, 9], [4, 10], [3, 7]]
컴퓨터를 최소 몇 대를 구매해야 모든 학생이 컴퓨터를 사용할 수 있을까?

접근 방법

앞의 실습 강아지 밥그릇 문제에서 result가 배열로 선언되어 있었다는 것에서 아이디어 얻음!! 배열 안의 공간 = 컴퓨터 라고 생각하고 각각의 사용 완료 시간을 표시하는 방식으로 풀 생각~!

일단, 가장 효율적으로 사용하기 위해서는, 끝나는 시간이 가장 이른 사람부터 컴퓨터를 사용해야 하므로 배열을 정렬할 때, 우선순위를 끝나는 시간 > 시작하는 시간 순서대로 정렬한다. last 배열을 선언하고 배열의 길이 = 컴퓨터의 개수라고 생각하고, 각각의 컴퓨터를 마지막으로 사용을 끝낸 시간을 표시한다. 정렬된 배열을 하나씩 살펴보면서 n번째 사람의 시작 시간보다 빨리 컴퓨터 사용을 끝낸 사람이 있다면, 그 컴퓨터를 사용한다.

예를 들면,

# 컴퓨터를 모두 사용할 수 없는 경우 #
last = [3, 4, 7] #index 0, 1, 2 컴퓨터 각각의 사용이 끝나는 시간이 3시, 4시, 7시라고 가정
sortedTimes[4] = [2, 6]
sortedTimes[4][0] = 2 #5번째 사람이 컴퓨터 사용을 시작하는 시간이 2시라면

여기에서 5번 학생이 2시에 컴퓨터를 사용하려면 새로운 컴퓨터를 구매해야 한다.

last.append(sortedTimes[4][1]) #5번째 학생이 컴퓨터 사용 마치는 시간을 last 리스트에 추가
last = [3, 4, 7, 6]

또 다른 경우,

# 사용할 수 있는 컴퓨터가 있는 경우 #
last = [3, 4, 7, 6] 
sortedTimes[5] = [4, 6]
sortedTimes[5][0] = 4 #6번 학생이 컴퓨터 사용을 시작하는 시간이 4시라면

이 경우에 6번째 사람은 4시에 컴퓨터를 사용하고 싶어 하고, index 0 의 컴퓨터는 3시에 사용이 끝났으므로 사용할 수 있다.

last[0] = sortedTimes[5][1] #6번 학생이 컴퓨터를 사용 완료한 시간을 넣어 준다.

그런데 여기서 문제가 발생함… last 배열 안에 sortedTimes[x][0]보다 작거나 같은 요소가 있는가? 만 알아본다면 간편했을 테지만 우리는 그 값의 인덱스를 찾아서 다시 값을 넣어주어야 한다. 그래서 chatGPT의 도움을 구했다….

‘배열 안에서 조건을 만족하는 첫 번째 원소의 인덱스 값을 찾고 싶어’ 라고 하니까 친절하게 알려 주었다.

    # 구매해야 하는 컴퓨터의 최소 개수를 계산해 주세요.
    last = [0]
    for x in range(len(sortedTimes)):
            # last 배열에서 조건을 만족하는 첫 번째 값의 index 찾기
        if any(y <= sortedTimes[x][0] for y in last) == True:
            idx = next(i for i, val in enumerate(last) if val <= sortedTimes[x][0]) 
            last[idx] = sortedTimes[x][1]
        else:
            last.append(sortedTimes[x][1])
        # print(last)
    return len(last) -1

any를 활용해서 조건을 만족하는 y가 존재한다면, y값을 새로운 값으로 덮어씌우는 것이다. 나는 여기서 냅다 y를 쓰면 알아서 할당이 되는 줄 알았으나, 인덱스를 따로 찾아야 했다. (안일했다…. ^^)

인덱스를 찾기 위해 사용된 기능이 next와 enumerate이다. 뭔지 몰랐지만 지금부터 공부해 보도록 할게~!

여기서 드는 의문점. 가장 먼저 등장하는 걸 사용하는 것보다 배열 안에서 (기존 배열 안의 종료 시간 - new 시작 시간) 값이 최소인 요소를 찾아서 리턴하는 게 컴퓨터실을 더 효율적으로 활용할 수 있을 것 같지만 난 아직 감자기 때문에 첫 번째로 등장하는 값의 인덱스를 찾았다.

Full Solution 1

def minimunComputerNeeds(times):
    result = 0
    # 이용 시간을 정렬해요.
    # 종료 시간이 빠른 순서 & 시작 시간이 빠른 순서
    sortedTimes = sorted(times, key = lambda x: (x[1],x[0]))
    # print(sortedTimes)
    
    # 구매해야 하는 컴퓨터의 최소 개수를 계산해 주세요.
    last = [0]
    for x in range(len(sortedTimes)):
            # last 배열에서 조건을 만족하는 첫 번째 값의 index 찾기
        if any(y <= sortedTimes[x][0] for y in last) == True:
            idx = next(i for i, val in enumerate(last) if val <= sortedTimes[x][0]) 
            last[idx] = sortedTimes[x][1]
        else:
            last.append(sortedTimes[x][1])
        # print(last)
    return len(last) -1

def main():
    n = int(input())
    times = []
    for _ in range(n):
        time = [int(x) for x in input().split()]
        times.append(time)
    print(minimunComputerNeeds(times))

if __name__ == "__main__":
    main()

이렇게 풀었지만 꼭 인덱스를 찾지 않아도 문제를 풀 수 있었다. 그냥 조건에 맞는 값을 찾고 remove 한 다음 새로운 종료 시간을 append 해 주면 되는 거였다.

Full Solution 2

def minimunComputerNeeds(times):
    result = 0
    # 이용 시간을 정렬해요.
    # 종료 시간이 빠른 순서 & 시작 시간이 빠른 순서
    sortedTimes = sorted(times, key = lambda x: (x[1],x[0]))
    # print(sortedTimes)
    
# 구매해야 하는 컴퓨터의 최소 개수를 계산해 주세요.
    last = [0]
    for x in range(len(sortedTimes)):
					# 그냥 삭제하자! 
        if sortedTimes[x][0] >= min(last):
            last.remove(min(last))
            last.append(sortedTimes[x][1])
        else:
            last.append(sortedTimes[x][1]) #추가로 필요한 컴퓨터의 개수를 구해야 하기 때문에 -1

def main():
    n = int(input())
    times = []
    for _ in range(n):
        time = [int(x) for x in input().split()]
        times.append(time)
    print(minimunComputerNeeds(times))

if __name__ == "__main__":
    main()

728x90

알고리즘 문제/AI & 알고리즘 스터디