[알고리즘][Python] 백준(BOJ) 1026 보물_파이썬

1-3. 탐색과 정렬(2)

A - 1026 보물    https://www.acmicpc.net/problem/1026

1026번: 보물

 

 

 

 

 

문제 풀기 전 공부할 것 : 정렬, 탐색

 

 

 

 

 

 

 

풀이 1

• A의 최소와 B의 최대를 짝 지어주면 된다.
• B를 재배열하면 안 되므로 A를 sort()하고 B의 최대의 index를 A와 연결해준다.

 

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()    # A 정렬
b = B.copy()    # B는 재배열하면 안되므로 B.copy()

a = dict()
for i in range(N):
    idx = b.index(max(b))
    a[idx] = A[i]
    b[idx] = -1       # N번 동안 max의 index를 찾아야 하므로
    
a = sorted(a.items())
for i, j in a:
    A[i] = j

S = 0
for i in range(N):
    S += A[i]*B[i]     # B는 재배열하지 않음
print(S)

 

+) a를 dict()로 하지 않고 index를 받아 풀 수 있을 것 같다.

+) 더 깔끔하고 간단한 풀이가 있을 것.

 

 

풀이 2

이걸 B가 재배열 안 된 거라고 해도 되는지 모르겠다.

 

2-1)

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

res = 0
for _ in range(N):
    res += A.pop(A.index(min(A))) * B.pop(B.index(max(B)))
    
print(res)

2-2)

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

def pair_min_max(A, B):
    res = 0
    A.sort()
    for i in A:
        m = max(B)
        res += i * m
        B.pop(B.index(m))
    return print(res)

pair_min_max(A, B)

 

 

시도 1 ==> 런타임 에러

• B의 가장 큰 원소에 A의 가장 작은 원소를 매치한다.
• A를 정렬하고 순서대로 B의 가장 큰 원소와 매치시킨다.
• B의 가장 큰 원소 순의 인덱스 리스트를 만든다.

 

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.sort(reverse=True)
b_dic = dict()
a = []

for idx, ele in enumerate(B):
    b_dic[ele] = idx
b = sorted(b_dic.items())

for i in range(N):
    a.append((A[i], b[i][1]))
a.sort(key=(lambda x : x[1]))

S = 0
a_n = []
for i in range(N):
    a_n.append(a[i][0])
    S += a_n[i] * B[i]

print(S)

+) 딱 봐도 복잡해보이고 정신없는 코드이다.

 

 

 

 

 

 

 

 

 

* 분명 B에 있는 수는 재배열하면 안 된다고 나와 있는데 문제를 해결하고 나서 다른 사람의 풀이를 찾아보니 그냥 B를 재배열한 사람이 많았고 그렇게 제출해도 문제가 없어 보였다.

* 따라서 이 문제는 A의 최소와 B의 최대를 곱하여 더한다는 것이 핵심이고 이에 따라 A, B를 정렬할 수 있는지 묻는 문제라는 생각이 들었다.

* B를 재배열하지 않으려고 많은 생각을 하였는데 허무하기도 하다.

 

 

 

 

 

 

복습

• 위치 반환(index)

index(x) 함수는 리스트에 x값이 있으면 x의 위치 값을 돌려준다.

* 리스트에 x값이 존재하지 않으면 값 오류(ValueError)가 발생한다. *

a = [1, 2, 3]
a.index(3)
#  2
a.index(1)
#  0

 

• dictionary(딕셔너리) 정렬

- dictionary 키(key) 기준 정렬

정렬(sort)하면 기본으로 키(key)를 기준으로 정렬한다.

d = {1:21, 3:14, 4:23, 2:1, 0:10}
sorted(d)
#  [0, 1, 2, 3, 4]
sorted(d.keys())
#  [0, 1, 2, 3, 4]

 

- dictionary 값(value) 기준 정렬

value 기준으로 정렬하려면 key 매개 변수에 lambda 함수를 사용하여 value 값을 기준으로 정렬하라고 하면 된다.

d = {1:21, 3:14, 4:23, 2:41, 0:10}
sorted(d, key = lambda x : d[x])
#  [0, 3, 1, 4, 2]

 

- dictionary.items() 정렬

items()를 사용하면 튜플(tuple) 항목들로 이루어진 목록을 만들어 준다. 이것 역시 사전의 key 기준으로 정렬된다.

d = {1:21, 3:14, 4:23, 2:41, 0:10}
d.items()
#  dict_items([(1, 21), (3, 14), (4, 23), (2, 41), (0, 10)])
sorted(d.items())
#  [(0, 10), (1, 21), (2, 41), (3, 14), (4, 23)]

값(value) 기준으로 정렬하려면 lambda 함수를 사용하면 된다.

d = {1:21, 3:14, 4:23, 2:41, 0:10}
sorted(d.items(), key = lambda x : x[1])   # x : 튜플 => x[1] : 값(value)
#  [(0, 10), (3, 14), (1, 21), (4, 23), (2, 41)]

 

• enumerate(), zip()

- enumerate() : index 번호와 원소를 tuple 형태로 반환

l = [1, 4, 8, 23, 32, 43]
for x in enumerate(l):
	print(p)
    
#  (0, 1)
#  (1, 4)
#  (2, 8)
#  (3, 23)
#  (4, 32)
#  (5, 43)

- zip(*iterable) : 동일한 개수로 이루어진 자료형을 묶어 주는 역할

list(zip([1, 2, 3], [4, 5, 6]))
#  [(1, 4), (2, 5), (3, 6)]
list(zip('abc', 'def'))
#  [('a', 'd'), ('b', 'e'), ('c', 'f')]

 

• 정렬 - [].sort(*, key=None, reverse=Flase), sorted(iterable, /, *, key=None, reverse=False)

sort(), sorted() 함수는 리스트의 요소를 순서대로 정렬해 준다.

- key = function(customize the sort order)

- reverse = False(descending order) / True(ascending order)

 

sort() : 원본 리스트를 정렬하지만 반환 값은 None이고 원본 리스트의 순서를 변경한다.

l = [4, 1, 3, 2]
print(l.sort())
#  None
print(l)
#  [1, 2, 3, 4]

sorted() : 정렬된 새로운 리스트를 반환하고(원본 리스트에 영향 없음) 모든 iterable에 동작한다.

l = [4, 1, 3, 2]
print(sorted(l))
#  [1, 2, 3, 4]
print(l)
#  [4, 1, 3, 2]

* sort()는 원본 리스트 순서를 변화시키고 sorted()는 정렬된 새로운 리스트를 반환한다. => sort()는 새로운 복사본을 만들지 않기 때문에 sorted()보다 빠르다.