[python] 백준 11399 : ATM

문제에 대한 최종풀이는 맨 아랫부분에 작성된 코딩입니다 (그 전까진 그냥 푸는과정을 주저리주저리 써놓은 스토리텔링(?)형식입니다)

 

주어진 입력값을 크기 순으로 재배치하는 정렬(sort)문제입니다. 정렬은 알고리즘 공부를하면서 굉장히 많이 사용되는 개념인데요.. 문제를 보며 생각해봅시다. P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 만큼 시간이 걸릴때 그냥 입력받은 순서대로 배치해버리면 각 사람별 소요되는 시간의 총합이 3+(3+1)+(3+1+4)+(3+1+4+3)+(3+1+4+3+2)만큼 발생합니다. 이 총합이 최소가 되게 하려면 어떻게해야될까요? 계산규칙을 보면 자신의 소요시간이 앞사람의 소요시간에 계속 누적해서 더해지는 방식입니다. 그렇다면, 순서상 1번사람의 소요시간t는 1번부터 5번의 소요시간에 모두 더해지겠지요. 2번의 소요시간은 2번부터 5번까지... 그렇다면 많이 더해지는 t값의 크기가 작을수록 총합이 작아질겁니다. (가중치가 가장 높은 position에 가장 작은 변수를 할당하는겁니다.)

마치 우리가 편의점에서 물건을 살때 나는 음료수 한개만 사면되는데 내 앞사람이 음료수에 과자랑 라면을 한바가지씩 사서 계산하느라 다같이 늦어지는일을 방지하기위해 알바가 말하죠. 뒤엣분 먼저 계산 해드리겠다고.

우리도 소요시간이 가장 적은 고객님 순으로 정렬을 해주면 되는겁니다. 총합 계산은 그 뒤에 생각하죠.

 

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

def pic(a):
    for i in range(len(a)-1):
        min_idx = i
        for j in range(i+1,len(a)):
            if a[j]<a[min_idx]:
                min_idx=j
            a[i],a[min_idx]=a[min_idx],a[i]

    return a
    
print(pic(a))

선택정렬의 가장 일반적인 알고리즘 형태입니다.

n은 인원수, a은 인원별 소요시간을 입력받아 바로 리스트에 할당합니다. (이때 리스트는 입력순서대로 정렬됩니다.)

이제 입력순서대로 정렬된 리스트를 숫자 크기순 오름차순으로 정렬해줘야 합니다. for문을 이용해 리스트의 n-2번째 요소까지 비교하는겁니다. 

문법이 나타내는 논리방식을 해석해봅시다. 첫번째 for문에서 i를 0번(리스트상 첫번째 요소)부터 n-2번(리스트상 뒤에서 두번째 요소)까지 할당해 리스트상 위치를 바꿔가며 비교해줍니다.

두번째 for문에서 j에는 i+1부터 리스트의 끝까지를 할당하여, a[i]와,  a[i+1]부터 a[n]까지 값의 대소비교를 합니다.

만약 입력 리스트 a =[15, 26, 32, 7, 4]라고 해봅시다. 이 문법에 의하면

리스트의 첫항인 15와, 15의 뒤에있는 모든 요소와 대소비교를 해서, 만약 뒤에 15보다 작은 요소값이 있다면, 해당 요소와 15와의 위치를 바꾸는겁니다. (return위에 적힌 문법처럼 파이썬에선 x,y = y,x과 같은 표현을통해 x와 y의 값을 서로 바꿔줄수있습니다.)

a = [15,26,32,7,4]의 경우 동작하는 양상을 같이 봅시다.

i=0일때 a[min_idx]=15입니다. (초기 최솟값을 일단 15로 할당합니다.) 그후 i+1부터 n까지 즉, 리스트상 두번째 요소부터 끝까지 대소비교를 하는겁니다. 두세번째 요소인 26,32는 15보다 크므로 if문에 걸리지 않습니다. 그러나 7이 걸리는데요,

if문에 걸리므로 이제 min_idx = 3 (7의 위치값)이 됩니다. 그리고 a[0]과 a[3]의 위치가 바뀌게 되죠 (위치 바꾸는것이 for문 안에 있지만, 앞서 26,32와 비교할때는 i=min_idx이므로 그냥 자기자신과 위치를 바꾸는 (결국 제자리..) 동작입니다.

그러나 이제는 min_idx가 바뀌었으므로 실제로 위치를 바꿔야겠죠. 7까지 검사한결과 리스트 a=[7,26,32,15,4]입니다.

아직 아래 for문에 대한 동작이 끝나지 않았습니다. 끝까지 가야죠. (range(len(a))면 range(5)인데, 파이썬에서 range함수는 마지막 값을 포함시키지 않습니다. 그렇기에 4번째 항까지만 검사를 하면 됩니다. 그러나 리스트의 위치값이 0부터 시작하므로 사실상 range(n)은 위치상 끝까지 검사하는것과 같습니다.)

근데 아직 i=0인데 a=[7,26,32,15,4]이므로 a[0]값이 바뀌었습니다. (위치 바꿔주는 동작이 매번 j가 업데이트 될때마다 시행되므로 실시간으로 바뀝니다.) 이때 또 a[j]<a[min_idx]값을 충족시킵니다. (7<4) 그럼 i=0일때 모든 j에 대해 for문 동작을 마쳤을때 업데이트 되는 리스트는 a=[4,26,32,15,7]이 됩니다. 

 

이제 i=1부터 이 과정을 반복하면 됩니다. i=1이므로 26부터 시작해주면 됩니다. 이제는 26과의 비교입니다. 

i=1일때 리스트 a의 업데이트 양상을 작성해보면 a=[4,26,32,15,7] → a=[4,15,32,26,7] → a=[4,7,32,26,15]입니다.

i=2일때는 32와의 비교이므로  a=[4,7,32,26,15] → a=[4,7,26,32,15] → a=[4,7,15,32,26]입니다.

i=3일때 (range(4)까지 이므로 마지막 검사입니다.)  a=[4,7,15,32,26] → a=[4,7,15,26,32]이죠. 

 

최종적으로 a=[4,7,15,32,26]로 우리가 원하는대로 순차적으로 정렬이 됐습니다. 0부터 위치를 바꿔가며 뒤엣값과 비교하는 알고리즘이죠. 이 방법이 선택정렬입니다.

 

이제 문제로 돌아가면, 이 순차정렬한 값을 이용해 시간값의 총합을 구해야합니다.

위에 시간 총합 계산식을 보면  3+(3+1)+(3+1+4)+(3+1+4+3)+(3+1+4+3+2) 처럼 3xn + 1x(n-1) + 4x(n-2).... 처럼 

길이가 n인 리스트의 0번째 요소에는 n이, 1번째 요소에는 n-1이... i번째 요소에는 n-i이 곱해지는 형태입니다.

간단한 for문을 돌리면 되겠죠

 

앗! 그런데!

위에서 짠 코드에 문제의 입출력 예시값인 3 1 4 3 2를 입력하면 리스트에 [2, 1, 3, 3, 4]로 저장되어 출력하는걸 볼 수 있습니다. 정렬이 꼬였는데 어디서부터 잘못된거지...? 바로 입력에 중복되는값이 있을때를 고려하지 못한 부분에서 꼬인걸겁니다. 위의 코드는 입력값이 서로 중복되지 않을때의 상황을 가정으로 짠겁니다.. 

그냥 퉁치고 넘어가고싶지만 현실세계에선 입력값이 중복되는 경우가 있을수있으므로 꾹참고해봅시다 인생에 어려운일이 이것뿐이겠어요?

이모티콘 추가 기능을 이제봤네요 일단 지금 저처럼 얼타는 라이언을 보면서 잠시 뇌에 휴식을 준뒤 다시 시작해봅시다.

 

일단 위 방식의 문제점은 하나의 리스트에서 자리를 바꿔가며 작업을 수행했기에 중복값이 발생하는경우 계산이 꼬일수 있다는겁니다 (항상 꼬이는것은 아니고, 입력순서에 따라 후루꾸로 잘 나오는경우도 있습니다만 이건 언제까지나 운의 영역이므로..)

 

그럼 '새로운 빈 리스트를 생성해서 반복문 수행별 추출된 최솟값을 입력리스트에서 빼서 빈 리스트에 차례로 넣는 방법은 어떨까?'  이렇게된다면 중복값이 순서대로 배열되지 않을때 (ex. 3 4 3 으로 배열되어있는 상황. 맨처음 3의 입장에선 4도 자신보다 작지않고 3도 자신보다 작지않으므로 저 배열에 대해 문제없는것으로 판단하고 반복문 종료.) 어쨌든 중복값인 3은 맨 앞에 한개는 위치해있으므로, 이 3을 리스트에서 빼낸다면 나머지 3은 유일한값이 됩니다 (중복값이 여러개더라도, 배열은 엉망이지만 어쨌든 최솟값만 정확하다면 괜츈)

 

이제, 위에서 기술한 방법에서 최솟값 발생시 리스트 내에서 위치를 바꾸는게 아닌, 최솟값을 추출해 빈 리스트에 순서대로 입력하는 방식을 사용해봅시다.

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

def pic(a):
    min_idx=0
    for i in range(1,len(a)):
        if a[i]<a[min_idx]:
            min_idx=i
    return min_idx

result=[]
while a:
    min_val = a.pop(pic(a))
    result.append(min_val)

sum_val =0
for j in range(n):
    val=(n-j)*result[j]
    sum_val += val

print(sum_val)

 

a.pop은 리스트에서 인덱스에 해당하는 값을 추출하는 기능을 합니다. 새롭게 정의된 빈 리스트 result에 순서대로 min_val을 삽입한다. 마지막으로 위의 계산규칙대로 j번째 값에 (n-j)을 곱해 다 더해주면 시간의 합을 구할수있습니다

 

정렬의 기초에대해 알아봤는데 꽤나 우여곡절을 겪어 당황했고... 부지런히 닦고 조이고 기름칠하겠읍니다..... (정비병 출신 (아님))