[백준] 11399번 ATM - Python(2편)

백준 문제 연결 링크입니다.

https://www.acmicpc.net/problem/11399

 

2024.12.09 - [코딩 테스트] - [백준] 11399번 ATM - Python(1편)

[백준] 11399번 ATM - Python(1편)

앞의 글이랑 이어지는 글입니다.

 

1편에서는 주어지는 데이터를 오름차순으로 정렬한 후, 정렬된 리스트를 순회하면서 각 사람의 대기 시간을 더해나갔습니다만, 제가 이 문제를 처음 풀 당시에는 이렇게 풀지 않았고 정렬을 통해 가장 짧은 인출 시간을 가진 사람부터 처리함으로써 전체 대기 시간을 최소화하며, 각 인출 시간이 전체 합에 기여하는 횟수를 계산하여 문제를 해결했습니다.

 

말로 설명하면 복잡하니 코드를 보며 확인해 보겠습니다. 아래는 전체 코드입니다.

N = int(input())
data = list(map(int, input().split()))

data.sort()
time = 0
for i in range(len(data)):
    time += data[i]*(len(data)-i)

print(time)

 

이번 시간에는 전체를 분석하기 보다 1편이랑 차이점만 확인해 보겠습니다.

1. 총 대기 시간 계산

   time = 0
   for i in range(len(data)):
       time += data[i]*(len(data)-i)

    
   • time을 변수로 사용하여 총 대기 시간을 누적합니다.
   • 각 사람의 인출 시간 data[i]에 (len(data)-i)를 곱합니다. 이는 해당 사람의 인출 시간이 총 몇 번 더해지는지를 나타냅니다.

이런 식으로 최종적으로 계산된 time 값을 출력하는 코드입니다.

 

1편의 코드와 2편의 코드 둘 다 문제를 정확히 해결하지만 차이점이 있습니다.

시간 복잡도는 두 코드 모두 O(N log N)으로 동일합니다. 하지만 연산 횟수에서 2편의 코드는 단 한 번의 반복문으로 결과를 계산하는 반면, 1편의 코드는 두 개의 변수(waiting_time, total_time)를 사용하여 두 번의 덧셈 연산을 수행합니다.

 

이뿐만 아니라 메모리 사용에서도 차이가 있습니다. 변수가 1편이 더 많기 때문에 메모리 사용량은 2편이 더 적습니다. 2편의 코드가 메모리 사용을 더 최적화했다고 할 수 있겠습니다. 

 

하지만 1편의 코드는 약간 더 길지만 각 단계가 명확히 구분된다는 점, 그리고 직관성이 뛰어나다는 장점이 있습니다.

 

---

 

 

추가) 아래는 파이썬을 더 파이썬스럽게 사용하기 위해 리스트 컴프리헨션을 사용하여 더 간략히 구현한 코드입니다.

N = int(input())
data = list(map(int, input().split()))

print(sum(t * (len(data) - i) for i, t in enumerate(sorted(data))))

1. sorted(data)
   • data 리스트를 오름차순으로 정렬합니다.
   • sort() 메서드와는 다르게 원본 리스트를 변경하지 않고 새로운 정렬된 리스트를 반환합니다.
2. enumerate(sorted(data))
   • 정렬된 리스트의 각 요소에 대한 인덱스 값의 쌍을 생성합니다.
   • i는 인덱스, t는 각 대기 시간을 나타냅니다.
3. t*(len(data)-i)
   • 각 대기 시간 t에 대한 가중치를 계산합니다.
   • (len(data)-i)는 해당 시간(t)이 총 대기 시간에 기여하는 횟수입니다.
4. for i, t in ... 구문
   • 리스트 컴프리헨션을 사용하여 각 요소에 대해 계산을 수행합니다.
5. sum(...)
   • 계산된 모든 값의 합을 구합니다.

 

 

#이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.