[정렬] 백준 #11399 ATM 인출 시간 계산하기 - Python

📚 문제

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

11399번: ATM

 

💡 접근법

정렬된 리스트에서 적절한 삽입 위치를 찾아 현재값을 삽입하는 삽입 정렬 알고리즘을 이용하여 구현하였다.

삽입 정렬이란?
이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방법이다.

 

💻 코드

1) 전체 코드

import sys

N = int(sys.stdin.readline())
num_list = list(map(int, sys.stdin.readline().split()))

sorted_list = [num_list[0]]
for i in range(1, N):
    curr_num = num_list[i]
    sorted_list.append(curr_num)
    for j in range(i-1, -1, -1):
        if sorted_list[j] > curr_num:
            sorted_list[j], sorted_list[j+1] = sorted_list[j+1], sorted_list[j]
        else:
            break

temp_sum = 0
result = 0
for i, n in enumerate(sorted_list):
    temp_sum += n
    result += temp_sum

print(result)

 

2) 해설

(1) 패키지 Import

import sys

파이썬 내장 함수인 input()보다 빠르게 값을 입력받기 위해 sys 라이브러리를 사용하였다.

 

(2) 입력받기

N = int(sys.stdin.readline())
num_list = list(map(int, sys.stdin.readline().split()))

사람의 수(N)를 입력받고 int로 형변환하였다.

각 사람이 돈을 인출하는 데 걸리는 시간을 입력받고 map()과 split()을 이용하여 각각의 요소를 int로 변환하고 list로 저장하였다.

 

(3) 삽입 정렬 구현

sorted_list = [num_list[0]]
for i in range(1, N):
    curr_num = num_list[i]
    sorted_list.append(curr_num)
    for j in range(i-1, -1, -1):
        if sorted_list[j] > curr_num:
            sorted_list[j], sorted_list[j+1] = sorted_list[j+1], sorted_list[j]
        else:
            break

1. num_list[0]의 값을 정렬된 리스트(sorted_list)의 초기값으로 넣어두고 인덱스 1부터 N까지 반복문을 통해 num_list를 순회한다.
2. 인덱스(i)에 해당하는 값을 sorted_list에 append한다.
3. sorted_list에 추가한 값(curr_num)을 삽입할 위치를 탐색하기 위해 추가한 값을 제외한 마지막 인덱스(i-1)부터 거꾸로 순회한다.
4. 만약 sorted_list[j] > curr_num이라면 sorted_list[j]와 sorted_list[j+1]을 swap한다.
5. 만약 sorted_list[j] > curr_num이 아니라면 적절한 위치에 curr_num을 삽입했으므로 break를 통해 빠져나온다.

 

(4) 출력하기

temp_sum = 0
result = 0
for i, n in enumerate(sorted_list):
    temp_sum += n
    result += temp_sum
    
print(result)

• temp_sum에는 각 사람이 돈을 인출하는 데 걸리는 시간(Pi)을 계산하여 저장한다.
• result에는 모든 사람이 돈을 인출하는 데 걸리는 시간을 계산하여 저장한다.

 

✅ 정답 확인

 

---

포스팅한 내용에 대한 조언/지적/피드백 모두 환영입니다!

읽어주셔서 감사합니다^.^