백준 > Python3 > 9070번 : 장보기

이번에 풀어볼 문제는 장보기라는 문제입니다. 순서대로 정렬하는 문제라고 볼 수 있는데요.

여기서는 정렬의 기준이 2개가 주어지는데 순차적으로 기준이 사용되는 케이스에요.

다른 분들은 어떻게 푸는지 잘모르겠지만 저같은 경우는 weight(가중치)를 부여해서

정렬할때 사용하는 값을 만들어서 정렬을 시켜요. 여기서는 sorted를 사용하니

이 가중치 적용과 sorted함수가 포인트겠네요.

문제

평소 맛살을 즐겨 먹는 혜선은 맛살을 구입하러 2-마트에 갔다. 

식품코너에서 맛살을 고르면서 혜선은 고민이 되기 시작했다. 

여러 업체에서 나온 맛살들이 들어있는 개수도 다르고 

가격도 다르기 때문에 어떤 것을 사야 싼 가격에 많이 먹을 수 있을지 

생각해야 했기 때문이다. 

혜선은 현명하게도 각 맛살에 써진 중량(g)과 가격(원)을 

다 조사해서 같은 가격으로 최대한 많은 중량을 살 수 있는 맛살을 사기로 했다. 

혜선의 고민을 해결해 줄 프로그램을 작성하시오.

입력/출력

입력

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스는 첫째 줄에는 맛살의 종류 N이 주어지고 두 번째 줄부터는 각 맛살의 중량(g) W와 가격(원) C가 순서대로 공백 하나를 사이에 두고 한 줄에 하나씩 N개가 주어진다. (1 ≤ N ≤ 100, 1 ≤ W ≤ 5000, 1 ≤ C ≤ 100000, W와 C는 정수)

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 혜선이 사야 하는 맛살의 가격을 한 줄에 하나씩 출력하시오. 같은 가격으로 살 수 있는 최대 중량이 같은 맛살이 두 개 이상인 경우는 낮은 가격의 것을 사기로 한다. 

예제입력	예제출력
3 2 300 2000 200 1500 3 320 2139 700 3200 1400 6400 5 250 1920 500 2980 430 2700 380 2350 340 2310	2000 3200 2980

풀이

일단 sorted 함수를 먼저 알아보도록하죠!

sorted함수는 입력되는 리스트를 정렬해서 새로운 리스트를 만들어

반환해주는 함수입니다. 사용하고 있는 리스트를 정렬하고 싶다면

리스트객체의 sort메서드를 사용하면 되는거에요.

예를들어 

a=[1,10,9,4]

라는 리스트가 있고 이 a 리스트를 정렬하고 싶다면

a.sort()를 사용하시면 되구요.

나는 a는 그대로 두고 새로운 리스트를 만들고 싶다!

그러면 sorted(a)라고 하시면 됩니다.

자 sort메서드도 그렇고 sorted함수도 그렇고 기본적으로

작은값부더 시작해서 큰값으로 차례대로 들어가는 리스트를

만들어줘요. 하지만 나는 다른 기준으로 정렬을 하고 싶을때는 어떻게 하지?

혹은 리스트에 들어있는 각각의 요소들이 단순히 값이 아니라

하나의 객체 혹은 리스트나 튜플일 경우는??

a=[(1,2), (30,2) . (-3.100)] 이런 경우에는 어떻게 정렬을 하는건가요??!!!라고

생각하실거에요.

이런 경우에는 key라는 인자를 사용하면 되요.

key라는 인자로 함수를 전달하고 그 함수는

정렬의 기준이 되는 값을 만드는 역할을 하는거죠.

위의 리스트 a의 경우를 보면

각 튜플의 index 0을 기준으로 정렬하는 경우와

index 1을 기준으로 정렬을 하는 케이스를 보여드릴게요.

index 0을 기준으로 하는 경우

sorted(a, key=lambda i: i[0])

index 1을 기준으로 하는 경우

sorted(a, key=lambda i: i[1])

여기서 lambda함수를 사용했는데요. 람다는 함수의 또다른 형식인데요.

< lambda 인자: 결과값 >의 형식으로 자주 사용되니 정확히 어떤건지는 몰라도

어떻게 사용하시는지만 이해하시면 충분할듯해요.

보면 람다함수가 인자로 i를 받고 각 i를 인덱스로 접근하고 있죠??

이 i는 a에 들어있는 각각의 요소들이에요. 그래서 이 함수의 결과값들을

기준으로 이 a라는 리스트를 정렬하는 거죠.

그리고 나서는 우리가 알아야하는 부분은 가중치를 추가해야하는 부분인데요.

같은 가격으로 살 수 있는 최대 중량이 같은 맛살이 두 개 이상인 경우는 낮은 가격의 것을 사기로 한다. 

라고 되어있죠?? 만약에 같은 가격으로 살수 있는 최대중량만 있다면 가격을 중량으로 나눈수로 리스트를 정렬해주면 되는데요.

하지만 이 경우에는 그 나눈 수가 같을 경우 낮은 가격을 사기로 되어있네요. 그러면 나온 결과값들 중에서

가격을 통해서 한번 더 정렬해주면 되는데요. 하지만 이렇게 하면 2번 정렬하는거라.

저는 잘하지 않고 한번에 해결하는데요. 방법은 먼저 정렬을 행해야하는 대상의 값에 가중치를 두는 방법이에요.

sorted(a, lambda i : i[0]/i[1]) 원래는 이렇게 하면 같은 값들 중에서 아무거나 정렬된 상태에 따라서

선택이 되는 데요.

여기서 이 값에 가중치를 주는거에요.

sorted(a, lambda i : i[1]/i[0]*10000000+i[1])

여기서는 가중치를 10000000배 만큼 곱해줬어요. 보통은 이렇게 10의 배수의 수로 곱해주는데요

그 기준은 뒤에 더해지는 값이 앞의 값에 덧셈에 의해서 영향을 주지않을 만큼의 길이만큼 곱해줘야해요.

만약 i[1]/i[0] 의 값이 134 이라고 하고 i[1]이 45234이라고 했을때 이 두수가 그냥 더해지면

합해진 값에는 134와 45234가 더 이상 존재하지 않게 되요.

하지만 134*10^6일경우에는 134045234로 134와 45234가 모두 이 수에 남아있게 되는데요.

이 경우에는 두 가지 기준으로 비교가 가능해지는거에요.

이러한 방식으로 풀면 끝!^^