99클럽 코테 스터디 _ 17일차 TIL (그리디)

 

< 문제 >

[백준] 11399. ATM / 실버4

---

< 풀이 >

코드 변수 정의

• times : 각 사람이 돈을 인출하는 데 걸리는 시간 리스트

---

Greedy
시간복잡도 : O(N^2)

def atm():
    N = int(input())
    times = list(map(int, input().split())) # 각 사람이 돈을 인출하는 데 걸리는 시간
    times.sort() # 대기 시간을 최소화하기 위해 오름차순 정렬

    ans = sum([sum(times[:i+1]) for i in range(N)]) # 각 사람이 기다려야 하는 총 시간 계산
    return ans

print(atm())

 

 

 

풀이 방식

1. 오름차순 정렬
   • 기다리는 시간의 합을 최소로 하려면, 처리 시간이 짧은 사람부터 먼저 인출해야 한다.
   • [3, 1, 4, 3, 2]가 주어졌다면, [1, 2, 3, 3, 4]로 정렬한다.
2. 총 대기 시간 계산
   • 각 사람이 기다려야 하는 총 시간을 구해야 한다.
   • 각 사람의 대기 시간 = 이전 사람들까지의 대기 시간 합 + 본인의 처리 시간
   • 각 사람이 대기한 시간을 모두 더한 값을 도출한다.
   • 문제 ) [1, 2, 3, 3, 4]로 정렬한 후, 각 사람들의 대기 시간
     • 1번째 사람 : 1
     • 2번째 사람 : 1 + 2 = 3
     • 3번째 사람 : 1 + 2 + 3 = 6
     • 4번째 사람 : 1 + 2 + 3 + 3 = 9
     • 5번째 사람 : 1 + 2 + 3 + 3 + 4 = 13
   • 총 대기 시간 : 1 + 3 + 6 + 9 + 13 = 32

 

---

< 회고 >

🤔 💭_

ATM 인출 대기 시간은 앞에서 기기에 소요하는 시간이 짧은 사람들이 올수록 인출하는 데 필요한 시간이 최소가 될 수 있다고 생각할 수 있었다. 그래서 시간순으로 먼저 오름차순 정렬을 한 후, 각 사람들의 대기 시간 합을 구하는 방식으로 코드를 구현했다. 

 

---

위 코드에서는 다음 코드와 같은 중첩된 sum() 연산으로 인해 비효율적으로 수행된다.

sum([sum(times[:i+1]) for i in range(N)])

 

 

[sum(times[:i+1]) for i in range(N)]

• range(N)을 사용하여 i = 0부터 N-1까지 반복한다.
• times[:i+1]는 times 리스트에서 앞에서부터 (i+1)개의 원소를 슬라이싱한다.
• sum(times[:i+1])은 슬라이싱한 리스트의 모든 요소를 더한다.

i	times[:i+1] 길이	sum(times[:i+1]) 연산량
0	1	O(1)
1	2	O(2)
2	3	O(3)
...	...	...
N-1	N	O(N)

• 전체 연산량

 

 

---

누적합(Prefix Sum)

누적합을 이용하여 코드를 최적화 한다.

 

시간 복잡도 : O(N logN)

def atm():
    N = int(input())
    times = list(map(int, input().split()))
    times.sort()

    total, current = 0, 0
    for t in times:
        current += t  # 현재 사람이 대기한 총 시간
        total += current  # 모든 사람의 대기 시간 합

    return total

print(atm())