경매는 여러 사람이 하나의 물건을 사려고 할 때, 각 사람이 원하는 가격을 제시하면 그 중 가장 높은 가격으로 물건을 팔게 되는 방식이다. 이러한 고전적인 경매 방식은 꽤 널리 쓰이는데, 최근에는 인터넷 쇼핑몰에서 반대의 경매 방식을 택하기도 한다. 즉, 여러 사람이 가격을 제시하면, 그 중 가장 낮은 가격으로 물건을 팔게 되는 방식도 쓰인다.
하지만 이럴 경우, 모든 사람들이 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()을 쓴다고 뜨지는 않지만 다른 문제를 풀 때 참고해볼만할거같다.
항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.
파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.
항승이는 길이가 L인 테이프를 무한개 가지고 있다.
항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.
물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.
입력
첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.
코드
n, l = map(int, input().split(' '))
line = list(map(int, input().split(' ')))
line = sorted(line)
answer = 0
left_position = line[0] - 0.5
for i in line:
right_position = i + 0.5
if left_position < right_position:
left_position = i + l - 0.5
answer += 1
print(answer)
해결
예를들어 파이프에 5개의 구멍이 있고 테이프의 길이는 1이라고 하자
그리고 1, 2, 3, 4, 5 x 좌표에 구멍이 났다고 하자
수리공 성격에는 구멍난곳 좌우로 0.5 만큼은 테이프를 붙여야한다고 하니
수리공이 갖고있는 테이프의 길이는 1 즉 구멍난곳 모두 테이프 하나로 막아야한다
이러한 경우는 어떤가
테이프의 길이가 2라서 1, 2좌표의 구멍을 막을 수 있다.
그러면 어떻게 풀어야할까
먼저 테이프를 칠할 시작 기준점(left)을 정해주자 처음 시작이니까 현재 0번째 인덱스의 요소 - 0.5 지점에 하면 되겠다
그리고 현재 요소를 테이프로 막는 위치는 요소의 + 0.5 지점(right)으로 매번 지정해주자
테이프를 한번 칠해볼까?
0.5에서 테이프길이 2를 더하면 2.5. 0.5에서 2.5까지 테이프가 칠해졌다.
아직 for문에서 1번이고 테이프를 칠한 마지막 위치 = 이제 테이프를 칠할 위치 기준점(left)는
테이프 길이만큼 칠하고 - 0.5 위치 이다.
그래서 1에서 2만큼 칠하면 3 거기다가 -0.5 해주면 2.5가 left가 되는거다!
그럼 2 지점은 테이프를 칠해야할지 아닌지 확인해볼까?
이미 1번 구멍에서 2까지 테이프를 칠했으니 칠할필요가 없다
이렇게 left < right 조건이면 칠하는걸로 한다면 테이프를 칠해야하는지 아닌지 알수있다
알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.
입력
첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.
출력
첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.
코드
my_dict = dict()
letters = input().upper()
for i in letters:
my_dict[i] = my_dict.get(i, 0) + 1
max_value = max(my_dict.values())
if list(my_dict.values()).count(max_value) == 1:
for key, value in my_dict.items():
if value == max_value:
print(key)
break
else:
print('?')
다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다.
1부터 8까지 차례대로 연주한다면 ascending, 8부터 1까지 차례대로 연주한다면 descending, 둘 다 아니라면 mixed 이다.
연주한 순서가 주어졌을 때, 이것이 ascending인지, descending인지, 아니면 mixed인지 판별하는 프로그램을 작성하시오.
입력
첫째 줄에 8개 숫자가 주어진다. 이 숫자는 문제 설명에서 설명한 음이며, 1부터 8까지 숫자가 한 번씩 등장한다.
출력
첫째 줄에 ascending, descending, mixed 중 하나를 출력한다.
코드
line = list(map(int, input().split(' ')))
ascending_flag = False
descending_flag = False
for i in range(1, len(line)):
if line[i-1]+1 == line[i]:
ascending_flag = True
elif line[i-1]-1 == line[i]:
descending_flag = True
else:
ascending_flag = False
descending_flag = False
break
if ascending_flag:
print('ascending')
elif descending_flag:
print('descending')
else:
print('mixed')
또는
line = list(map(int, input().split()))
if line == sorted(line):
print('ascending')
elif line == sorted(line, reverse=True):
print('descending')
else:
print('mixed')
해결
+1 또는 -1 해서 맞으면 ascending, descending 으로 출력하는데 아니면 mixed 하고 for문 탈출 하는 방법과
오름차순, 내림차순 정렬을하고 그것과 같으면 해당 출력 아니면 mxied 하는 방법 두가지가 있다
"OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수는 3이 된다.
"OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다.
OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 0보다 크고 80보다 작은 문자열이 주어진다. 문자열은 O와 X만으로 이루어져 있다.
출력
각 테스트 케이스마다 점수를 출력한다.
코드
count = int(input())
for i in range(count):
answer = 0
tmp = 0
line = input()
for j in line:
if j == 'O':
tmp += 1
answer += tmp
else:
tmp = 0
print(answer)
