018 ATM

배웠던 모든 종류의 버블을 사용해보도록 하자!

 

먼저 해당 문제는 삽입 정렬을 적용해보기 위한 문제이다!

그리고 추가로 아래 과정을 진행한다.

- 버블 정렬

- 선택 정렬

- sort

 

첫번째 코드 - 삽입 정렬

 

특정 범위를 골라서 해당 범위에서 target값이 어디에 위치해야하는지 찾고,

해당 위치에 끼워넣는 방법이다

 

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))

for i in range(n):
    target_data = A[i]
    left_interval = A[i+1:]
    
    for j in range(i):
        if target_data < A[j]:
            interval = A[j:i]
            A = A[:j] + [target_data] + interval + left_interval
            break

 

cum = []
cum_num = 0
for i in A:
    cum_num += i
    cum.append(cum_num)

print(sum(cum))

 

통과!

---

두번째 코드 - 버블 정렬

 

오름차순으로 정렬하는 것은 동일하므로 버블 정렬을 이용하여 정렬해보자!

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))

for i in range(n):
    for j in range(n-i-1):
        if A[j] > A[j+1]:
            temp = A[j]
            A[j] = A[j+1]
            A[j+1] = temp

 

cum = []
cum_num = 0
for i in A:
    cum_num += i
    cum.append(cum_num)

print(sum(cum))

 

통과!

---

세번째 코드 - 선택 정렬

 

뒤에서부터 거꾸로 진행하여 오름차순으로 만드는 코드이다

 

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))

for i in range(n):
    for j in range(n-1, i, -1):
        if A[j] < A[j-1]:
            temp = A[j]
            A[j] = A[j-1]
            A[j-1] = temp

 

cum = []
cum_num = 0
for i in A:
    cum_num += i
    cum.append(cum_num)

print(sum(cum))

 

통과!

---

네번째 코드 - sort

 

가장 단순하게 sort를 적용하여 오름차순으로 정렬한 후 계산한다.

 

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))

A.sort()

 

cum = []
cum_num = 0
for i in A:
    cum_num += i
    cum.append(cum_num)

print(sum(cum))

 

통과!

 

위의 모든 코드들 중 가장 시간이 적게 걸리는 과정이 sort 문이다.

버블 정렬은 시간이 오래 걸리므로 사용시 잘 생각해보아야 한다.

---

링크 (첫번째 코드)

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/11399.%E2%80%85ATM

programmers/백준/Silver/11399. ATM at main · ornni/programmers