[백준 2238번 문제, 파이썬3] 경매

문제

문제

경매는 여러 사람이 하나의 물건을 사려고 할 때, 각 사람이 원하는 가격을 제시하면 그 중 가장 높은 가격으로 물건을 팔게 되는 방식이다. 이러한 고전적인 경매 방식은 꽤 널리 쓰이는데, 최근에는 인터넷 쇼핑몰에서 반대의 경매 방식을 택하기도 한다. 즉, 여러 사람이 가격을 제시하면, 그 중 가장 낮은 가격으로 물건을 팔게 되는 방식도 쓰인다.

하지만 이럴 경우, 모든 사람들이 1원에 물건을 사겠다고 하는 사태가 발생할 수 있다. 따라서 같은 가격을 제시한 사람이 둘 이상일 경우에는 무효로 하는 방식이 쓰인다. 하지만 모든 가격을 여러 사람이 제시하는 경우도 있을 수 있기 때문에, 다음과 같은 방식으로 경매 당첨자를 선택하기로 한다.

우선 가장 적은 수의 사람이 제시한 가격을 찾는다. 이러한 경우가 여럿 있다면, 가장 낮은 가격으로 물건을 팔게 된다. 이때, 그 가격을 제시한 사람들 중에서 가장 먼저 제시한 사람이 물건을 살 수 있게 된다.

각각의 사람들이 제시한 가격이 주어졌을 때, 경매에 낙찰(당첨)되는 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 U(1 ≤ U ≤ 10,000), N(1 ≤ N ≤ 100,000)이 주어진다. U는 금액의 상한이고, N은 경매에 참여한 회수이다. 다음 N개의 줄에는 사람 이름 S(공백 없는 알파벳 대소문자 10자 이하)와, 그 사람이 제시한 가격 P(1 ≤ P ≤ U, 정수)이 경매에 참여한(가격을 제시한) 순서대로 주어진다.

출력

첫째 줄에 낙찰된 사람의 이름과 그 가격을 출력한다.

---

코드

import sys

u, n = map(int, sys.stdin.readline().split())  # 상한가, 경매 횟수를 입력받는데 빠른 입출력을 위해 sys 모듈을 사용한다
people_dict = dict()    # 경매 현황을 '경매가':['사람1', '사람2'] 형식으로 저장하려고 함

for _ in range(n):
    s, p = sys.stdin.readline().split()    # 사람과 경매가를 입력
    if int(p) <= u:
        people_dict[p] = people_dict.get(p, list()) + [s]    # 입찰가가 상한가를 초과하지 않은 건만 경매 등록

# 딕셔너리에서 입찰자의 수가 가장 적은 수를 추출
min_count = min([len(i) for i in people_dict.values()])
# 입찰자 수가 가장 적은 입찰가 중에서 최소 가격을 선택하고 입찰가들 중 첫 번째로 입찰 등록한 입찰가를 낙찰자로 선택
min_key = min([int(i) for i in people_dict.keys() if len(people_dict[i]) == min_count])

print(people_dict[str(min_key)][0], min_key)

---

해결

백준 경매 문제는 테스트 케이스가 적을뿐더러 문제 자체도 말을 꼬아놓았기 때문에 문제를 이해하는데 시간이 많이 쓰였다. 일반적으로 생각하는 최고 입찰가를 부른 사람에게 낙찰하는 것이 아니라 최소 입찰가를 부른 사람이 낙찰되는 경매 시스템을 구현하는 것이다.

 

여기서 봐야할것은 경매 시스템의 낙찰자 선정 방식이다. 다음은 해당 문제의 경매 시스템이다.

우선 가장 적은 수의 사람이 제시한 가격을 찾는다. 이러한 경우가 여럿 있다면, 가장 낮은 가격으로 물건을 팔게 된다. 이때, 그 가격을 제시한 사람들 중에서 가장 먼저 제시한 사람이 물건을 살 수 있게 된다.

문장을 하나씩 떼어놓고 이해해보자 "가장 적은 수의 사람이 제시한 가격을 찾는다"  이 말은 입찰가를 부른 사람의 수가 가장 적은 입찰가들을 선택하라는 뜻이 된다.

 

그리고 "이러한 경우가 여럿 있다면, 가장 낮은 가격으로 물건을 팔게 된다." 이 문장은 선택된 입찰가 중에 가장 저렴한 입찰가로 낙찰된다는 뜻이고,

 

"그 가격을 제시한 사람들 중에서 가장 먼저 제시한 사람이 물건을 살 수 있게 된다." 이 문장은 그 입찰가를 가장 먼저 부른 사람이 최종적으로 낙찰된다는 뜻이 된다.

 

문제에서 요구하는 문장을 이해하게 되면 입출력을 이해할 수 있다.

 

 

해당 문제의 입력은

상한가 경매 횟수(4)

사람이름1 입찰가

사람이름2 입찰가

사람이름3 입찰가

사람이름2 입찰가

 

출력은

사람이름2 입찰가

 

이런식으로 입출력이 이뤄진다.

 

해당 문제에서 "따라서 같은 가격을 제시한 사람이 둘 이상일 경우에는 무효로 하는 방식이 쓰인다." 이 문장만 읽고

최소 입찰가에서 중복되는 경매건을 제거하고 다음으로 최소인 가격을 부른 사람을 낙찰자로 선택하게 된다고 생각할수도있다. 테스트 케이스에서 중복되는 경매건 CD 5, Fe5 를 제외하고 그 다음으로 최소 값인 CD 7 을 낙찰자로 선택한다면 말은 되기 때문이다. 

 

하지만 해당 풀이 방법은 틀렸고, 정답은 다음처럼 접근해야한다.

가장 입찰가들의 수가 최소가 되는 입찰가를 선택한다.

예제 입력에서는 Lew 10과 CD 7이 각각 1명의 입찰자로서

즉, 입찰자들의 수가 최소인 1인 입찰가 10, 7을 선택할 수 있다.

 

그런다음 입찰가에서 가장 저렴한 입찰가를 선택한다. 즉, 7을 선택하며

7을 부른 사람중 첫번째인 CD를 낙찰자로 선택할 수 있다.

그렇게 되면 출력은 CD 7이 된다.

 

그리고 내가 딕셔너리로 사용한 이유가 입찰가에 따른 입찰자들의 수를 좀 더 편리하게 뽑아 내기 위해 사용했다

{

    '10':['Lew'],

    '5':['CD', 'FE'],

    '7':['CD'

} 

 

그리고 sys 모듈을 사용하고 안하고 차이를 이번 문제를 풀면서 실감하게 되었다.

input() 메서드를 그냥 쓸 때 단지 그차이인 코드인데도 거의 30배 정도 차이가났으니 이제는 sys 모듈로 입력을 받으려고 한다. 물론 시간초과는 input()을 쓴다고 뜨지는 않지만 다른 문제를 풀 때 참고해볼만할거같다.

---

참고

링크