첫번째 문제
모험가 길드
N명의 모험가를 대상으로 공포도를 측정했다. 해당 공포도보다 많은 수의 그룹에 들어가야 여행을 떠날 수 있다. 그룹 수의 최대값을 구하는 프로그램을 작성하시오.
입력조건
- 첫째 줄에 모험가의 수 N이 주어집니다.(1 <= N <= 100,000)
- 둘째 줄에 각 모험가의 공포도 값을 N이하의 자연수로 주어지며, 각 자연수는 공백으로 구분합니다.
출력 조건 - 여행을 떠날 수 있는 그룹 수의 최댓값을 출력합니다.
# 입력 예시
>>> 5
>>> 2 3 1 2 2
# 출력 예시
2문제풀이
정렬 후 사람의 수를 세는데 이번 차례의 공포도와 사람 수가 같으면 그 사람을 포함해서 한 묶음으로 처리하면 된다.
# 사람의 수
n = int(input())
# 공포도 리스트
array = list(map(int, input().split()))
# 정렬하기
array = sorted(array)
result = 0
cnt = 0
for i in array:
cnt += 1
if cnt >= i:
result += 1
cnt = 0
print(result)두번째 문제
곱하기 혹은 더하기
각 자리가 숫자로만 이루어진 문자열이 주어질 때, 왼쪽에서 오른쪽으로 하나씩 모든 숫자를 확인하며 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
# 입력 예시
>>> 02984
# 출력 예시
576# 입력 예시
>> 567
# 출력 예시
210문제풀이
# 문자열 받기
data = input()
# 첫 시작 수를 대입
result = int(data[0])
for s in data[1:]:
num = int(s)
# 둘 중에 하나라도 1 이하의 수가 있다면 덧셈
if num <= 1 or result <= 1:
result += num
# 아니라면 곱셈
else :
result *= num
print(result)세번째 문제
문자열 뒤집기
네번째 문제
만들 수 없는 금액
N개의 동전을 이용해 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.
입력조건
- 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다.(1<= N <= 1000)
- 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수입니다.
# 입력 예시
>>> 5
>>> 3 2 1 1 9
# 출력 예시
8문제풀이
먼저 정렬을 진행한다.
target을 1부터 시작하여 확인하며 이번 차례의 동전보다 target이 작은 경우, 해당 target은 만들 수 없는 금액이 된다.
# 동전의 개수
n = int(input())
# 동전 화폐 단위를 나타내는 수(개수 이기도 함)
array = list(map(int, input().split()))
array.sort()
# 표현할 화폐는 1부터 시작함
target = 1
for i in array:
# 이번 차례의 화폐보다 target이 작으면
if target < i:
break
#
target += i
print(target)다섯번째 문제
볼링공 고르기
A, B 두 사람이 볼링을 치고 있다. 서로 무게가 다른 볼링공을 고르려고 할 때 경우의 수를 구하시오.
입력 조건
- 첫째 줄에 볼링공의 개수 N,공의 최대 무게 M이 공백으로 구분되어 각각 자연수의 형태로 주어진다.
(1 <= N <= 1000, 1 <= M <= 10) - 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어진다.
(1 <= K <= M)
출력 조건 - 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력
# 입력 예시
5 3
1 3 2 3 2
# 출력 예시
>>> 8# 입력 예시
8 5
1 5 4 3 2 4 5 2
# 출력 예시
>>> 25문제풀이
combinations를 활용해 간단하게 풀 수 있다.
from itertools import combinations
# n : 공의 개수 m : 공의 최대무게
n, m = map(int, input().split())
balls = list(map(int, input().split()))
count = 0
for case in combinations(range(n), 2):
i, j = case
if balls[i] != balls[j] :
count += 1
print(count)하지만 해당 문제는 그리디 단원의 문제이므로 그리디 알고리즘을 활용하여 풀어보자.
무게별 개수를 파악하고, 자신보다 큰 무게의 개수와의 경우의 수를 구하여 더한다.
n, m = map(int, input().split())
data = list(map(int, input().split()))
# 1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11
for x in data:
# 각 무게에 해당하는 볼링공의 개수 카운트
array[x] += 1
result = 0
# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m + 1):
n-= array[i] # 무게가 i 인 볼링공의 개수(A가 선택할 수 있는 개수 제외)
result += array[i] * n # B가 선택하는 경우의 수와 곱하기
print(result)여섯번째 문제
무지의 먹방 라이브
문제링크
먹방 중 방송이 끊켰을 때 다음 차례에 먹을 음식의 인덱스를 출력하시오. 1초에 한 음식씩 순서대로 먹는다.
문제풀이
food_times를 우선순위 큐를 통해 낮은 것부터 꺼내서 k시간 내에 다 먹는 음식들을 먼저 제거한다.
이전까지 소비한 시간 + (현재의 음식 시간 - 이전 음식 시간)이 k보다 커지는 경우, 이후로 남은 음식들에 대해 순서대로 접근하여 음식번호를 출력한다.
(현재의 음식 시간 - 이전 음식 시간)인 이유는 이전까지 한바퀴를 돈다는 가정이므로 다같이 하나씩 빠진다는 것을 참고해야한다.
import heapq
def solution(food_times, k):
# 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
if sum(food_times) <= k:
return -1
# 시간이 작은 음식부터 뺴야하므로 우선순위 큐를 이용
q = []
for i in range(len(food_times)):
# (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
heapq.heappush(q, (food_times[i], i + 1))
sum_value = 0 # 먹기 위해 사용한 시간
previous = 0 # 직전에 다 먹은 음식 시간
length = len(food_times) # 남은 음식의 개수
# sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
while sum_value + ((q[0][0] - previous) * length) <= k:
now = heapq.heappop(q)[0]
sum_value += (now - previous) * length
length -= 1 # 다 먹은 음식 제외
previous = now # 이전 음식 시간 재설정
# 남은 음식 중에서 몇 번쨰 음식인지 확인하여 출력
result = sorted(q, key = lambda x : x[1]) # 음식의 번호 기준으로 정렬
return result[(k - sum_value) % length][1]해당 문서는 '이것이 코딩테스트다. with 파이썬 - 나동빈 저'를 읽고 정리한 내용입니다.
